题目大意

给你一个树形的网络，每条边从父亲流向儿子。根节点为原点，叶子节点流向汇点，容量为无穷大。

可以给一些边扩大容量，最多总共扩大\(m\)容量。每条边的容量有上限。

求扩大容量后最大的最大流。

思考历程

隐隐约约地猜到正解跟树链剖分有什么关系，可是没有打，也没有时间打。

只能暴力DP来水分。

设\(h_{i,j}\)为\(i\)的父亲到\(i\)的最大流，扩大了\(j\)次容量。\(g_{i,j}\)为\(i\)到子树的最大流，扩大了\(j\)次容量。前者由后者和边的容量取最小值后得到。

转移方程显然。

这样水了\(70\)分，超过预期\(20\)分。

正解

有个费用流的做法：对于每个父亲到儿子连费用不同的两条边。扩大一次相当于增加一点费用。

跑最小费用最大流，每次选费用最小的路来增广，费用不超过\(m\)时的最大流即为答案。

这种做法是\(O(n^2)\)的。因为每次增广过后至少会有一条边满流，相当于删掉了这条边。

题解说期望得分\(100\)……我真的服……然而真的有人这么打就过了……

正解是利用树的性质来优化费用流……题解说用\(LCT\)，我看打题解的人实在是太物流了。明明这题码量这么长，还打\(LCT\)？

接下来我们模拟费用流的过程：

找到一个从根节点到叶子节点的费用最小的路径。

求出这条路径的最大流量\(f\)（也就是路径上容量最小的边）。

统计入答案。

路径上的所有边的容量都减去\(f\)。

将修改过的路径上满流边找出来（即为容量为\(0\)的边）。分类讨论：如果费用为\(0\)，那就修改它的费用为\(1\)，并且修改它的容量；如果费用为\(1\)，标记这条边不能再经过（也就是所有的后代都不能到达）。

当然，记得要特殊判断一下即将大于\(m\)的情况。

这个东西用树链剖分和线段树来维护。线段树上维护这些信息：最小的容量\(f\)及其儿子的编号\(numf\)（某条从上到下的路径上容量最小的边），还有最小的费用\(w\)及叶子节点的编号\(numw\)（这个费用为根节点到叶子节点路径上费用之和）。

操作\(1\)的时候，就是询问最小的\(w\)。

操作\(2\)的时候，就是当前节点到根路径上最小的\(f\)。

操作\(4\)的时候，就是当前节点到根路径上的所有边区间减\(f\)。

操作\(5\)的时候，就是将当前节点能到的所有叶子节点的费用区间加\(1\)或无限大。

就是这些操作了……

代码

好长……还好树链剖分和线段树好打……

using namespace std;#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define N 10010#define INF 1000000000int n,m;struct EDGE{    int to;    EDGE *las;} e[N];int ne;EDGE *last[N];bool leaf[N];int a[N],b[N];int fa[N],siz[N],hs[N];int top[N],dfn[N],nowdfn,to_num[N];int noww[N];void dfs1(int x){    siz[x]=1;    for (EDGE *ei=last[x];ei;ei=ei->las){        fa[ei->to]=x;        dfs1(ei->to);        siz[x]+=siz[ei->to];        if (siz[ei->to]>siz[hs[x]])            hs[x]=ei->to;    }    if (siz[x]==1)        leaf[x]=1;}void dfs2(int x,int t){    top[x]=t;    dfn[x]=++nowdfn;    to_num[nowdfn]=x;    if (hs[x])        dfs2(hs[x],t);    for (EDGE *ei=last[x];ei;ei=ei->las)        if (ei->to!=hs[x])            dfs2(ei->to,ei->to);}struct Node{    int f,numf;    int w,numw;    int tagf,tagw;} seg[N*4];inline void updatef(int k){    if (seg[k<<1].f<=seg[k<<1|1].f)        seg[k].f=seg[k<<1].f,seg[k].numf=seg[k<<1].numf;    else        seg[k].f=seg[k<<1|1].f,seg[k].numf=seg[k<<1|1].numf;}inline void updatew(int k){    if (seg[k<<1].w<=seg[k<<1|1].w)        seg[k].w=seg[k<<1].w,seg[k].numw=seg[k<<1].numw;    else        seg[k].w=seg[k<<1|1].w,seg[k].numw=seg[k<<1|1].numw;}inline void pushdown(int k){    if (seg[k].tagf){        seg[k<<1].f+=seg[k].tagf;        seg[k<<1|1].f+=seg[k].tagf;        seg[k<<1].tagf+=seg[k].tagf;        seg[k<<1|1].tagf+=seg[k].tagf;        seg[k].tagf=0;    }    if (seg[k].tagw){        if (seg[k].tagw>=INF)            seg[k<<1].w=seg[k<<1|1].w=seg[k<<1].tagw=seg[k<<1|1].tagw=INF;        else{            seg[k<<1].w+=seg[k].tagw;            seg[k<<1|1].w+=seg[k].tagw;            seg[k<<1].tagw+=seg[k].tagw;            seg[k<<1|1].tagw+=seg[k].tagw;            seg[k].tagw=0;        }    }}void build(int k,int l,int r){    if (l==r){        if (leaf[to_num[l]])            seg[k]={a[to_num[l]],to_num[l],0,to_num[l],0,0};        else            seg[k]={a[to_num[l]],to_num[l],INF,0,0,0};        return;    }    int mid=l+r>>1;    build(k<<1,l,mid);    build(k<<1|1,mid+1,r);    updatef(k),updatew(k);}void changef(int k,int l,int r,int st,int en,int c){    if (st<=l && r<=en){        seg[k].f+=c;        seg[k].tagf+=c;        return;    }    pushdown(k);    int mid=l+r>>1;    if (st<=mid)        changef(k<<1,l,mid,st,en,c);    if (mid
         
          =INF) seg[k].w=seg[k].tagw=INF; else{ seg[k].w+=c; seg[k].tagw+=c; } return; } pushdown(k); int mid=l+r>>1; if (st<=mid) changew(k<<1,l,mid,st,en,c); if (mid
          
            un(const pair
           
             &a,const pair
            
              &b){return a.first<=b.first?a:b;}pair
             
               queryf(int k,int l,int r,int st,int en){ if (st<=l && r<=en) return {seg[k].f,seg[k].numf}; pushdown(k); int mid=l+r>>1; pair
              
                res(INF,0); if (st<=mid) res=un(res,queryf(k<<1,l,mid,st,en)); if (mid
               
                >1; if (x<=mid) return queryw(k<<1,l,mid,x); return queryw(k<<1|1,mid+1,r,x);}inline int flow(int x){ int res=INT_MAX; for (;x;x=fa[top[x]]) res=min(res,queryf(1,1,n,dfn[top[x]],dfn[x]).first); return res;}inline void find(int x,int c){ for (int y=x;y;y=fa[top[y]]) changef(1,1,n,dfn[top[y]],dfn[y],-c); for (;x;x=fa[top[x]]){ while (x){ pair
                
                  tmp=queryf(1,1,n,dfn[top[x]],dfn[x]); if (tmp.first) break; if (noww[tmp.second]==0){ noww[tmp.second]=1; changew(1,1,n,dfn[tmp.second],dfn[tmp.second]+siz[tmp.second]-1,1); changef(1,1,n,dfn[tmp.second],dfn[tmp.second],b[tmp.second]); } else{ changew(1,1,n,dfn[tmp.second],dfn[tmp.second]+siz[tmp.second]-1,INF); x=fa[tmp.second]; } } }}int main(){ scanf("%d%d",&n,&m); a[1]=INT_MAX; for (int i=1;i<=n;++i){ int u,v; scanf("%d%d",&u,&v); u++,v++; e[ne]={v,last[u]}; last[u]=e+ne++; scanf("%d%d",&a[v],&b[v]); b[v]=min(b[v]-a[v],m); } n++; dfs1(1),dfs2(1,1); build(1,1,n); int ans=0; while (1){ int x=seg[1].numw,cost=seg[1].w; if (cost>=INF) break; int plus=flow(x); if (m

总结

有的时候网络流是可以用数据结构维护的……

转载于:https://www.cnblogs.com/jz-597/p/11329599.html

你可能感兴趣的文章

[leetcode] 309. Best Time to Buy and Sell Stock with Cooldown(medium)