学习笔记 - 带上下界的网络流 | Lucky_Glass's Blog
0%

学习笔记 - 带上下界的网络流

都说了是网络流专场……写篇博客防止自己忘掉(结果在以后的某一次考试的时候碰到一道上下界网络流,然后“?我好像学过上下界网络流……怎么做的来着?”)

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
/*Lucky_Glass*/
#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]/*in-out*/,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
/*Lucky_Glass*/
#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,欢迎提问!