都说了是网络流专场……写篇博客防止自己忘掉(结果在以后的某一次考试的时候碰到一道上下界网络流,然后“?我好像学过上下界网络流……怎么做的来着?”)
lskao同学自学上下界还上台给所有同学讲课,66666(投币~)
Part0. 上下界网络流
Tab. 以下基于 lskao 同学的讲课以及我自己的一些理解。
“上下界网络流”,顾名思义,就是每条边 $(u,v)$ 有它的上界 $c(u,v)$ 和下界 $l(u,v)$。这里的上下界是对于流量的上下界,即边 $(u,v)$ 的流量 $f(u,v)$ 要满足 $l(u,v)\leq f(u,v)\leq c(u,v)$。
一般的网络流只有上界,即边的容量,在此基础上我们加入下界……但是可能会有一些非常特别的流网络,下面细说。
Part1. 无源汇可行流(循环流)
没有源点、汇点,也就是说每个点必须要有入边和出边(没有入边就是源点、没有出边就是汇点,这样就不满足无源汇了)。
个人感觉没有源点汇点的网络流非常怪异,比如最初流网络里的流是从哪来的……实际上,无源汇可行流可以这样理解 —— 你需要给每条边 $(u,v)$ 一个流 $f(u,v)$,使得 $l(u,v)\leq f(u,v)\leq c(u,v)$ ,并且对于任意点满足“流入到它的流量=从它流出的流量”(流守恒性),问是否存在满足条件的 $f(u,v)$ 的方案。
对于这样的问题,我们考虑下面的做法:
对于每条边,令 $f(u,v)=l(u,v)$,即流量为它的下界。但是这样的流不一定满足流守恒性,于是我们称这个流为 “初始流”。
考虑新建一个流网络 $G’$,定义超级源点 $S$ 和超级汇点 $T$。
因为初始流的每条边上的流都取的是对应边的下界,所以我们不能减小一些边的流量来达到流守恒,只能增大流量。定义 $d(u)$ 表示 “流入点$u$的流量 - 流出点$u$的流量”,那么 $d(u)$ 可能为正负或0。
这里 $d(u)$ 有一个性质:$\sum_u d(u)=0$。
若 $d(u)>0$,则点 $u$ 需要连再流出 $d(u)$ 的流量,所以连一条从 $S$ 到 $u$ 的容量为 $d(u)$ 的边,如果该边流满了,说明 $u$ 在初始流中多的 $d(u)$ 的入流可以全部流出,也就是 $u$ 可以满足流守恒;
而若 $d(u)<0$,则点 $u$ 需要再流入一些流量,所以连一条从 $u$ 到 $T$ 的容量为 $-d(u)$ 的边,如果该边流满了,说明 $u$ 可以获得 $|d(u)|$ 的入流,从而满足流守恒性。
然后对于原图上的边 $(u,v)$ ,在 $G’$ 中建一条容量为 $c(u,v)-l(u,v)$ 的边,也就是这条边还可以流的流量。
这样建图后,跑最大流,检验从 $S$ 出发的所有边和到达 $T$ 的所有边是否流满,如果是,则存在可行流。
另外如果要求输出可行流的方案,令 $G’$ 中边 $(u,v)$ 的流量为 $f’(u,v)$,则原图的可行流中,边 $(u,v)$ 的流量 $f(u,v)=l(u,v)+f’(u,v)$,显然 $l(u,v)\leq f(u,v)\leq c(u,v)$。
· 一个版子
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
| #include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
const int N=200,M=10200,inf=(1<<29);
struct EDGE{int to,lim;EDGE *nxt,*rev;}*cop[N+10]; struct FLOWGRAPH{ EDGE edg[(M+N)*3],*top[N+10],*ncnt; FLOWGRAPH(){ncnt=edg;} void AddEdge(int u,int v,int lim){ EDGE *p=++ncnt,*q=++ncnt; *p=(EDGE){v,lim,top[u],q};top[u]=p; *q=(EDGE){u,0,top[v],p};top[v]=q; } }Gflw;
bool vis[N+3]; int n,m,Ps,Pt; int firio[N+3],rnk[N+10],El[M+3];
int GetFlow(int u,int flwin){ if(u==Pt) return flwin; int flwout=0; vis[u]=true; for(EDGE *it=cop[u];it;it=it->nxt){ cop[u]=it;int v=it->to; if(vis[v] || !it->lim || rnk[u]+1!=rnk[v]) continue; int flwv=GetFlow(v,min(flwin-flwout,it->lim)); it->lim-=flwv;it->rev->lim+=flwv; flwout+=flwv; if(flwin==flwout) break; } vis[u]=false; return flwout; } bool BFS(){ for(int i=1;i<=Pt;i++) rnk[i]=0; queue<int> que;que.push(Ps);rnk[Ps]=1; while(!que.empty()){ int u=que.front();que.pop(); for(EDGE *it=Gflw.top[u];it;it=it->nxt){ int v=it->to; if(!it->lim || rnk[v]) continue; rnk[v]=rnk[u]+1; if(v==Pt) return true; que.push(v); } } return false; } int Dinic(){ int ret=0; while(BFS()){ memcpy(cop,Gflw.top,sizeof Gflw.top); ret+=GetFlow(Ps,inf); } return ret; } int main(){ scanf("%d%d",&n,&m); Ps=n+1,Pt=n+2; for(int i=1;i<=m;i++){ int u,v,El,Eu; scanf("%d%d%d%d",&u,&v,&El,&Eu); firio[v]+=El;firio[u]-=El; Gflw.AddEdge(u,v,Eu-El); ::El[i]=El; } int eptflw=0; for(int u=1;u<=n;u++){ if(firio[u]<0) Gflw.AddEdge(u,Pt,-firio[u]); if(firio[u]>0){ Gflw.AddEdge(Ps,u,firio[u]); eptflw+=firio[u]; } } int res=Dinic(); if(res!=eptflw){ printf("NO\n"); return 0; } printf("YES\n"); for(int i=1;i<=m;i++){ int id=i*2-1; printf("%d\n",El[i]+Gflw.edg[id].rev->lim); } return 0; }
|
Part2. 有源汇可行流
(没想到有源汇还比无源汇麻烦一点点)
其实也没麻烦多少。
因为流守恒,流出源点的流量=流入汇点的流量,那么我们把汇点连向源点(因为流入汇点的流量可能为任意值,所以容量为 inf),然后忽略源点、汇点的特殊性(把他们当作普通点),不难发现这样的图仍然满足流守恒。
于是它就变成了 无源汇可行流,其他方法都一样了~
(没有版题,没有代码 >︿<)
Part3. 有源汇最大流
废话……最大流当然有源汇 awa
我们发现跑了有源汇可行流过后,我们不一定会得到原图的最大流……(也不是最小流 emm)
考虑怎么从一个可行流转变为最大流 ——
其实很好理解:因为网络流的增广操作本身就是在上一次增广后的 残留网络 上尝试增广,而我们跑了可行流过后就留下了一个残留网络,我们在这个残留网络上用 Dinic 增广从 原图上的源点 到 原图上的汇点 的路径就可以了(注意要与求可行流时额外建立的超级源点、汇点区别!),直到得到最大流就可以了。
但是这个网络上有一些边是为了判断是否可行而额外建立的(是不属于原图的边),比如从 原图上的汇点 连到 原图上的源点 的边、以及从 超级源点 出发或到达 超级汇点 的边。这些边不属于原图的残留网络,因此不能经过。在增广的时候对这些边特判一下……
Tab. 个人觉得不是特别方便计算最后流入汇点的流量,我的解决方法是把到达汇点的所有边的流量都加起来(注意 原图上边的流量=新图上的流量+流量下界)
· 一个版子
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
| #include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
const int N=202,M=9999,inf=(1<<29);
struct EDGE{int to,lim;EDGE *nxt,*rev;}*cop[N+10]; struct FLOWGRAPH{ EDGE edg[3*(M+N)],*ncnt,*top[N+10]; FLOWGRAPH(){ncnt=edg;} void AddEdge(int u,int v,int lim){ EDGE *p=++ncnt,*q=++ncnt; *p=(EDGE){v,lim,top[u],q};top[u]=p; *q=(EDGE){u,0 ,top[v],p};top[v]=q; } }Gflw;
int Ps,Pt,n,m,Qs,Qt; bool Ifmxflw; int firio[N+3],rnk[N+10],savEl[M+3]; bool vis[N+10];
int GetFlow(int u,int flwin,int Hs,int Ht){ if(u==Ht) return flwin; int flwout=0; vis[u]=true; for(EDGE *it=cop[u];it;it=it->nxt){ cop[u]=it; int v=it->to; if(!it->lim || vis[v] || rnk[v]!=rnk[u]+1) continue; if(Ifmxflw && ((it-Gflw.edg==1) || (it-Gflw.edg==2) || u==Qs || v==Qs || u==Qt || v==Qt)) continue; int flwv=GetFlow(v,min(it->lim,flwin-flwout),Hs,Ht); flwout+=flwv; it->lim-=flwv;it->rev->lim+=flwv; if(flwout==flwin) break; } vis[u]=false; return flwout; } bool BFS(int Hs,int Ht){ for(int i=1;i<=Qt;i++) rnk[i]=0; queue<int> que;que.push(Hs);rnk[Hs]=1; while(!que.empty()){ int u=que.front();que.pop(); for(EDGE *it=Gflw.top[u];it;it=it->nxt){ int v=it->to; if(!it->lim || rnk[v]) continue; if(Ifmxflw && ((it-Gflw.edg==1) || (it-Gflw.edg==2) || u==Qs || v==Qs || u==Qt || v==Qt)) continue; rnk[v]=rnk[u]+1; if(v==Ht) return true; que.push(v); } } return false; } int Dinic(int Hs,int Ht){ int totflw=0; while(BFS(Hs,Ht)){ memcpy(cop,Gflw.top,sizeof Gflw.top); totflw+=GetFlow(Hs,inf,Hs,Ht); } return totflw; } int main(){ scanf("%d%d%d%d",&n,&m,&Ps,&Pt); Gflw.AddEdge(Pt,Ps,inf); Qs=n+1,Qt=n+2; for(int i=1;i<=m;i++){ int u,v,El,Eu; scanf("%d%d%d%d",&u,&v,&El,&Eu); Gflw.AddEdge(u,v,Eu-El); firio[u]-=El;firio[v]+=El; savEl[i]=El; } int eptflw=0; for(int u=1;u<=n;u++){ if(firio[u]>0) Gflw.AddEdge(Qs,u,firio[u]); if(firio[u]<0){ Gflw.AddEdge(u,Qt,-firio[u]); eptflw+=-firio[u]; } } int flwres=Dinic(Qs,Qt); if(flwres!=eptflw){ printf("please go home to sleep\n"); return 0; } Ifmxflw=true; Dinic(Ps,Pt); int ans=0; for(int i=1;i<=m;i++){ int id=i*2+1; if(Gflw.edg[id].to==Pt) ans+=Gflw.edg[id].rev->lim+savEl[i]; } printf("%d\n",ans); return 0; }
|
The End
Thanks for reading!
Email: lucky_glass@foxmail.com,欢迎提问!