有上下界限制的网络流

## 几个概念 每一条边有容量上界和下界，要满足 下界$<=flow<=$上界 可行流：满足上下界限制，满足流量守恒，源点总流出量等于汇点总流入量 最大流：满足可行流前提下使流量最大 最小流：满足可行流前提下使流量最小 ------ ## $1.$无源无汇可行流 每条边有上下界限制的情况下，如果所有边都是按下界或是上界作为初始流，有可能不满足流量守恒。所以我们要 **将一个不满足流量守恒的初始流调整成满足流量守恒的流** 流量守恒,即每个点的总流入量=总流出量 如果存在一个可行流,那么一定满足每条边的流量都大于等于流量的下限。 因此我们可以令每条边的**流量等于流量下限**,得到一个初始流,然后建出这个流的残量网络.(即:**每条边的流量等于这条边的流量上限与流量下限之差**) 这个初始流不一定满足流量守恒，**因此最终的可行流一定是在这个初始流的基础上增大了一些边的流量使得所有点满足流量守恒.** 所以我们考虑一个能满足流量守恒的附加流,使得这个附加流和我们的初始流合并之后满足流量守恒 ### $(1)$建立一个超源s和超汇t ### $(2)$求出$du[i]$并连边 $du[i]=in[i]$（$i$节点所有入流下界之和）$-out[i]$（$i$节点所有出流下界之和）。 当$du[i]$大于$0$的时候，$s$到$i$连一条流量为$du[i]$的边。 当$du[i]$小于$0$的时候，i到t连一条流量为$-du[i]$的边。 ### $(3)$求$s$到$t$的最大流 若等于从$s$出发的所有边 即所有加到$s$的附加流都流满了 就说明有可行流。流量即为$maxflow$ **每条边在可行流中的流量=容量下界+附加流中它的流量(即跑完$Dinic$之后所加反向边的权值).** ------ ## $2.$有源有汇可行流 设源点为$s$，汇点为$t$ 怎么办呢？**要转化成无源无汇的做**。 即先从$t$到$s$连一条上界为 $inf$，下界为$0$的边。这样就转化成了一个无源无汇的图。再添加超 源$S$，超汇$T$，按刚才的方法求出可行流$flow1$ 那么最后得到的可行的有源汇流的流量$flow1$就等于**t到s的无穷边的流量(即dinic跑完之后反向边的权值)** ------ ## $3.$有源有汇最大流 设源点为$s$，汇点为$t$ ### $(1)$先求出有源有汇可行流 求可行流的流量$flow1=$**$t$到$s$的无穷边上跑出的流量** ### $(2)$在可行流的残量网络上跑是$s$——$t$的最大流 现在得到了可行流，但只是满足了下界，还可以继续增加。这时我 们要删除$S$和$T$，然后以s为源点，以t为汇点**在刚才求出的残量网络上**跑一边最大流得到flow2（注意不用删除$t$到$s$的无穷边） **$maxflow=flow1+flow2$** ------ ## $4.$有源有汇最小流 和最大流差不多 考虑反向边的意义相当于退流 所以走可行流加出的反向边就相当于减小了正向增广 ### $(1)$先求出有源有汇可行流 按照有源汇可行流建图 求可行流的流量$flow1=$**$t$到$s$的无穷边上跑出的流量** ### $(2)$继续退流 拆掉超级源点$S$和超级汇点$T$以及$t$到$s$的无穷边 跑$t$到$s$的最大流$flow2$ **$minflow=flow1-flow2$** 例如[$P4843$清理雪道](https://www.luogu.org/problemnew/show/P4843) ```cpp #include<bits/stdc++.h> using namespace std; const int maxn=10010; const int inf=1e9; struct edge{ int to,nxt,dis,f; }; edge e[maxn]; int head[maxn],tot,cur[maxn]; void add(int x,int y,int z) { e[++tot].to=y; e[tot].f=1; e[tot].dis=z; e[tot].nxt=head[x]; head[x]=tot; } int dep[maxn]; bool bfs(int s,int t) { memset(dep,0x3f,sizeof(dep)); memcpy(cur,head,sizeof(head)); queue<int>q; q.push(s);dep[s]=0; while(q.size()) { int x=q.front();q.pop(); for(int i=head[x];~i;i=e[i].nxt) { int y=e[i].to; if(!e[i].f)continue; if(dep[y]!=0x3f3f3f3f||!e[i].dis)continue; dep[y]=dep[x]+1; q.push(y); } } return dep[t]!=0x3f3f3f3f; } int dfs(int x,int t,int limit) { if(x==t||!limit)return limit; int f=0,flow=0; for(int i=cur[x];~i;i=e[i].nxt) { int y=e[i].to;cur[x]=i; if(!e[i].f)continue; if(dep[y]==dep[x]+1&&(f=dfs(y,t,min(e[i].dis,limit)))) { flow+=f;limit-=f; e[i].dis-=f;e[i^1].dis+=f; if(!limit)break; } } return flow; } int maxflow; void Dinic(int s,int t) { while(bfs(s,t)) maxflow+=dfs(s,t,inf); } int n,du[maxn]; int main() { tot=-1; memset(head,-1,sizeof(head)); scanf("%d",&n); int s=n*2+1,t=s+1,S=t+1,T=S+1; for(int i=1;i<=n;i++) { int num,x; scanf("%d",&num); for(int j=1;j<=num;j++){ scanf("%d",&x); du[x]++;du[i]--; add(i,x,inf); add(x,i,0); } add(s,i,inf);add(i,s,0); add(i,t,inf);add(t,i,0); } for(int x=1;x<=t;x++) { if(du[x]>0)add(S,x,du[x]),add(x,S,0); if(du[x]<0)add(x,T,-du[x]),add(T,x,0); } add(t,s,inf);add(s,t,0); Dinic(S,T);//有源有汇可行流 maxflow=0; int flow1,flow2; for(int i=head[s];~i;i=e[i].nxt)//删除t到s的边 if(e[i].to==t)flow1=e[i].dis,e[i].f=e[i^1].f=0;//可行流等于t到s无穷边上的流量 for(int i=head[S];~i;i=e[i].nxt)//删除S e[i].f=e[i^1].f=0; for(int i=head[T];~i;i=e[i].nxt)//删除T e[i].f=e[i^1].f=0; Dinic(t,s);//退流 flow2=maxflow; cout<<flow1-flow2;//有源有汇最小流 return 0; } ``` ------ ## $5.$有上下界的费用流 这里的费用流是在满足可行流条件下的最小费用 **因为是可行流 所以只用跑一边网络流 而最大流/最小流需要再从原始起点 终点跑一边** 其实和可行流差不多 ### $(1)$遍历每条边 设每条边为$ (x,y,l,r,c) $一开始遍历每一条边 把它变成$ (x,y,0,r-l,c) $并把$ans$加上$l*c$ 即让每条边流一个下界 ### $(2)$跑费用流 然后类似于可行流的构建方式根据每个点的$du$分别向起点和终点连边 如果有源点和汇点再连一条边权为$inf$的边 从超级源跑费用流 $S$的出边满流才有可行流 费用即为$mincost$ 如[$P4043 [AHOI2014/JSOI2014]$支线剧情](https://www.luogu.org/problem/P4043) ```cpp // luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; const int maxn=1e6+300; const int inf=1e9; struct edge{ int to,nxt,dis,cost; }e[maxn<<1]; int tot=-1,head[maxn]; void add(int x,int y,int l,int r,int cost) { e[++tot].to=y;e[tot].dis=r-l;e[tot].cost=cost;e[tot].nxt=head[x];head[x]=tot; e[++tot].to=x;e[tot].dis=0;e[tot].cost=-cost;e[tot].nxt=head[y];head[y]=tot; } int d[maxn],incf[maxn],vis[maxn],pre[maxn],mincost; bool spfa(int s,int t) { memset(incf,0x3f,sizeof(incf)); memset(vis,0,sizeof(vis)); memset(d,0x3f,sizeof(d)); queue<int>q; q.push(s);vis[s]=1;d[s]=0; while(q.size()) { int x=q.front();q.pop();vis[x]=0; for(int i=head[x];~i;i=e[i].nxt) { int y=e[i].to; if(e[i].dis<=0)continue; if(d[x]+e[i].cost<d[y]) { d[y]=d[x]+e[i].cost; if(!vis[y])q.push(y); incf[y]=min(incf[x],e[i].dis); pre[y]=i; } } } return d[t]!=0x3f3f3f3f; } void update(int s,int t) { int x=t; while(x!=s) { int i=pre[x]; e[i].dis-=incf[t];e[i^1].dis+=incf[t]; x=e[i^1].to; } } void EK(int s,int t) { while(spfa(s,t)) { mincost+=incf[t]*d[t]; update(s,t); } } int n,du[maxn]; int main() { memset(head,-1,sizeof(head)); scanf("%d",&n); int s=n+1,t=s+1,S=t+1,T=S+1; for(int x=1;x<=n;x++) { int num; scanf("%d",&num); for(int j=1;j<=num;j++) { int y,z; scanf("%d%d",&y,&z); du[x]--;du[y]++;//限制1次 add(x,y,1,inf,z); mincost+=z;//加上流满下界的贡献 } } add(s,1,0,inf,0); for(int i=1;i<=n;i++) add(i,t,0,inf,0); for(int i=1;i<=n;i++) { if(du[i]>0)add(S,i,0,du[i],0); if(du[i]<0)add(i,T,0,-du[i],0); } add(t,s,0,inf,0); EK(S,T); cout<<mincost; } ``` ## 思路 ``` 有源有汇最小流-->有源有汇最大流——>有源有汇可行流——>无源无汇可行流 ``` ------ [参考博客 https://www.cnblogs.com/liu-runda/p/6262832.html](https://www.cnblogs.com/liu-runda/p/6262832.html)