上下界网络流

OI&ACM, 网络流
  1. 无源汇
    1. 可行流
      1. 法一
      2. 法二
      3. 例：sgu 194
  2. 有源汇
    1. 可行流
      1. 例：POJ 2396
    2. 最大流
      1. 法一
      2. 法二
      3. 例：ZOJ 3229
    3. 最小流
      1. 法一
      2. 法二
      3. 例1：BZOJ 1458
      4. 例2：BZOJ 2502

上下界网络流就是边的流量有上下界限制的网络流
平常的网络流可以当做下界为0的特殊情况

无源汇

可行流

可以想到为了满足流量的下限 \(low\)，将边的流量设为 \(high-low\)。
但是求出这个图的最大流之后，加上 \(low\)，会使得某些点不满足流量平衡。
所以可以建立附加源和附加汇，来补充和吸收这些流量。

法一


由于下届是一条弧上的流必需要满足的确定值。下面引出必要弧的概念：必要弧是一定流要满的弧。必要弧的构造，讲容量下界的限制分离开了，从而构造了一个没有下界的网络\(G'\)：
1.将原弧\((u,v)\)分离出一条必要弧：\(c'(u,v)_ {nes}=b(u,v)\).（红色表示）
2.原弧：\(c'(u,v)=c(u,v)-b(u,v)\).
由于必要弧的有一定要满的限制，将必要弧“拉”出来集中考虑：
添加附加源\(x\)，附加汇\(y\)。想象一条不限上届的\((y,x)\)，有必要弧将它们“串”起来，即对于有向必要弧\((u,v)\)，添加\((u,y),(x,v)\)，容量为必要弧容量。这样就建立了一个等价的网络。
一个无源汇网络的可行流的方案一定是必要弧是满的。若去掉\((y,x)\)后，附加源\(x\)到汇\(y\)的最大流，能使得\(x\)的出弧或者\(y\)的入弧都满，充要于原图有可行流。
即对于一条边 \((u,v)\) ，在图中建三条边 \((u,v,high-low) , (S,v,low) , (u,T,low)\)

法二

发现上图中存在许多流量可以直接从 \(S\) 经过点 \(x\) 到 \(T\) ，这样的流量对答案没有贡献
所以考虑 \(du[i]\) 表示点 \(i\) 的入度-出度，则如果 \(du[i] > 0\)，建边 \((S,i,du[i])\)；否则建边 \((i,T,-du[i])\)。这样就省去了不少空间。

例：sgu 194

n个点，m根管道，里面单向流躺液体。
要使得m条管道组成一个循环体，并且满足每根都有流量限制[Li,Ri]。

1.建立原图中的边，\((u,v,high-low)\) 并 \(du[u]-=low , du[v]+=low\) ；
2.对于每个点i，如果 \(du[i] > 0\)，建边\((S,i,du[i])\)，否则建边\((i,T,-du[i])\) ；
3.如果\(maxflow (S,T) == \sum\limits_{du[i] > 0} du[i]\) ；

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
#include <cstdio>
#include <queue>
const int N=205;
int n,m,S,T,ans,ecnt=1,du[N],min[N*N],ds[N];
int head[N],to[N*N],rest[N*N],next[N*N];
std::queue<int> Q;
inline void Addedge(int x,int y,int r)
{
	to[++ecnt]=y;rest[ecnt]=r;next[ecnt]=head[x];head[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=0;next[ecnt]=head[y];head[y]=ecnt;
}
inline bool Bfs()
{
	for(int i=0;i<=T;i++) ds[i]=0;
	Q.push(S);ds[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int e=head[x],y=to[e];e;y=to[e=next[e]])
			if(rest[e]&&!ds[y])
				ds[y]=ds[x]+1,Q.push(y);
	}
	return ds[T];
}
inline int Maxflow(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(rest[e]&&ds[y]==ds[x]+1)
		{
			b=Maxflow(y,std::min(flow-a,rest[e]));
			a+=b;rest[e]-=b;rest[e^1]+=b;
			if(a==flow) break;
		}
	if(!a) ds[x]=0;
	return a;
}
int main()
{
	freopen("in.in","r",stdin);
	scanf("%d%d",&n,&m);
	T=n+1;
	for(int i=1,x,y,max;i<=m;i++)
	{
		scanf("%d%d%d%d",&x,&y,&min[i],&max);
		Addedge(x,y,max-min[i]);
		du[x]-=min[i];du[y]+=min[i];
	}
	for(int i=1;i<=n;i++)
	{
		if(du[i]>0) Addedge(S,i,du[i]),ans+=du[i];
		else if(du[i]<0) Addedge(i,T,-du[i]);
	}
	while(Bfs()) ans-=Maxflow(S,0x7fffffff);
	if(ans) printf("NO\n");
	else
	{
		printf("YES\n");
		for(int i=1;i<=m;i++)
			printf("%d\n",rest[i<<1^1]+min[i]);
	}
}

有源汇

可行流

从 \(T\) 向 \(S\) 连一条 \([0,inf]\) 的边，有源汇就变成了无源汇，就和上面一样了

例：POJ 2396

有一个 \(n\) 行 \(m\) 列的矩阵，每一行的和为 \(a[i]\)，每一列的和为 \(b[i]\)，对于一些点还有 \(>\) 或 \(=\) 或 \(<\) 的限制（ \(0\) 表示一整行或者一整列）。求满足条件的解。

对于每行和每列分别建一个点，\(s\) 与每行的点连 \([a[i],a[i]]\) 的边，每列的点与 \(t\)连 \([b[i],b[i]]\) 的边，中间连的边为点\((i,j)\) 的限制

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
int Case,n,m,E,s,t,S,T,ecnt,ans,min[201][21],max[201][21],du[250],ds[250];
int head[250],next[10000],to[10000],rest[10000];
std::queue<int> Q;
inline void Addedge(int x,int y,int r)
{
	to[++ecnt]=y;rest[ecnt]=r;next[ecnt]=head[x];head[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=0;next[ecnt]=head[y];head[y]=ecnt;
}
inline bool Bfs()
{
	for(int i=0;i<=T;i++) ds[i]=0;
	Q.push(S);ds[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int e=head[x],y=to[e];e;y=to[e=next[e]])
			if(rest[e]&&!ds[y])
				ds[y]=ds[x]+1,Q.push(y);
	}
	return ds[T];
}
inline int Maxflow(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(rest[e]&&ds[y]==ds[x]+1)
		{
			b=Maxflow(y,std::min(flow-a,rest[e]));
			a+=b;rest[e]-=b;rest[e^1]+=b;
			if(a==flow) break;
		}
	if(!a) ds[x]=0;
	return a;
}
int main()
{
	scanf("%d",&Case);
	while(Case--)
	{
		scanf("%d%d",&n,&m);
		s=n+m+1;t=n+m+2;T=n+m+3;
		ecnt=1;ans=0;
		memset(head,0,sizeof(head));
		memset(du,0,sizeof(du));
		memset(min,0,sizeof(min));
		memset(max,0x7f,sizeof(max));
		for(int i=1,x;i<=n;i++)
			scanf("%d",&x),du[s]-=x,du[i]+=x;
		for(int i=n+1,x;i<=n+m;i++)
			scanf("%d",&x),du[i]-=x,du[t]+=x;
		scanf("%d",&E);char ch[5];
		for(int i=1,x,y,z;i<=E;i++)
		{
			scanf("%d%d%s%d",&x,&y,ch,&z);
			if(ch[0]=='>') min[x][y]=std::max(min[x][y],z+1);
			else if(ch[0]=='<') max[x][y]=std::min(max[x][y],z-1);
			else min[x][y]=std::max(min[x][y],z),max[x][y]=std::min(max[x][y],z);
		}
		for(int i=1,x;i<=n;i++)
			for(int j=1;j<=m;j++)
			{
				min[i][j]=std::max(std::max(min[i][j],min[0][0]),std::max(min[i][0],min[0][j]));
				x=std::min(std::min(max[i][j],max[0][0]),std::min(max[i][0],max[0][j]))-min[i][j];
				ans|=(x<0);
				Addedge(i,n+j,x);du[i]-=min[i][j];du[n+j]+=min[i][j];
			}
		if(ans) { printf("IMPOSSIBLE\n\n");continue; }
		Addedge(t,s,0x7fffffff);
		for(int i=1;i<=t;i++)
			if(du[i]>0) Addedge(S,i,du[i]),ans+=du[i];
			else if(du[i]<0) Addedge(i,T,-du[i]);
		while(Bfs()) ans-=Maxflow(S,0x7fffffff);
		if(ans) { printf("IMPOSSIBLE\n\n");continue; }
		for(int i=1,num=1;i<=n;i++,printf("\n"))
			for(int j=1;j<=m;j++,num++)
				printf("%d ",min[i][j]+rest[num<<1^1]);
		printf("\n");
	}
}

最大流

法一

二分最大流量，判断是否可行
即 \(T\)->\(S\) 的边的流量为 \([x,inf]\)
1 . \(x>ans\) 即 \(min(T->S) > max(S->T)\) ,会使求新网络的无源汇可行流无解的（S,T流量怎样都不能平衡）
2 . \(x<=ans\) 会有解.

法二

1 . 连上 \(T\)->\(S\) 流量为 \(inf\) 的边，求一次附加源到附加汇的最大流，若不满流则无解
2 . 在残量网络上求一次 \(s\) 到 \(t\) 的最大流
3 . 答案就是第二次求出的最大流（因为第一次求出的最大流是 \(T\)->\(S\) 的流量，而这个流量在他的反向边 \(s\)->\(t\) 中出现，所以不需要另外加上）

第一次求出的最大流是为了满足 \(low\) 尽可能流满，然而此时 \(s\)->\(t\) 上可能还有可行的流，我们在残量网络上继续来求最大流，可以使得最后求出的流既满足 \(≥low\) 的限制，且最大。

例：ZOJ 3229

一个人给 \(m\) 个女神拍照，计划拍照 \(n\) 天，每天拍照数不能超过 \(Di\) 张，而且给每个女神 \(i\) 拍照有数量限制 \([Li,Ri]\)，对于每个女神n天的拍照总和不能超过 \(Gi\)，如果有解最多能拍多少张照，并求每天给对应女神拍多少张照；否则输出 \(-1\)。

\(s\) 到第 \(i\) 天连接 \([0,Di]\) 的边，第 \(i\) 个女神到 \(t\) 连接 \([Gi,inf]\) 的边 ; 对于每一天，当天到第 \(i\) 个女神连一条 \([Li,Ri]\) 的边。

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
#include <iostream>
#include <cstdio>
#include <queue>
const int inf=0x7fffffff;
int n,m,s,t,S,T,tot,ecnt,ans,du[1400],ds[1400],min[40000],E[40000];
int head[1400],next[90000],to[90000],rest[90000];
std::queue<int> Q;
inline void Addedge(int x,int y,int r)
{
	to[++ecnt]=y;rest[ecnt]=r;next[ecnt]=head[x];head[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=0;next[ecnt]=head[y];head[y]=ecnt;
}
inline bool Bfs()
{
	for(int i=0;i<=T;i++) ds[i]=0;
	Q.push(S);ds[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int e=head[x],y=to[e];e;y=to[e=next[e]])
			if(rest[e]&&!ds[y])
				ds[y]=ds[x]+1,Q.push(y);
	}
	return ds[T];
}
inline int Maxflow(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(rest[e]&&ds[y]==ds[x]+1)
		{
			b=Maxflow(y,std::min(flow-a,rest[e]));
			a+=b;rest[e]-=b;rest[e^1]+=b;
			if(a==flow) break;
		}
	if(!a) ds[x]=0;
	return a;
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		S=0;s=n+m+1;t=n+m+2;T=n+m+3;
		ecnt=1;ans=tot=0;
		for(int i=0;i<=T;i++) du[i]=head[i]=0;
		for(int i=1,x;i<=m;i++)
			scanf("%d",&x),Addedge(n+i,t,inf),du[n+i]-=x,du[t]+=x;
		for(int i=1,j,x,y;i<=n;i++)
		{
			scanf("%d%d",&j,&x);
			Addedge(s,i,x);
			while(j--)
			{
				scanf("%d%d%d",&x,&min[++tot],&y);
				Addedge(i,n+x+1,y-min[tot]);du[i]-=min[tot];du[n+x+1]+=min[tot];
				E[tot]=ecnt;
			}
		}
		Addedge(t,s,inf);
		for(int i=1;i<=t;i++)
			if(du[i]>0) Addedge(S,i,du[i]),ans+=du[i];
			else if(du[i]<0) Addedge(i,T,-du[i]);
		while(Bfs()) ans-=Maxflow(S,inf);
		if(ans) { printf("-1\n\n");continue; }
		S=s;T=t;
		while(Bfs()) ans+=Maxflow(S,inf);
		printf("%d\n",ans);
		for(int i=1;i<=tot;i++)
			printf("%d\n",rest[E[i]]+min[i]);
		printf("\n");
	}
}

最小流

法一

二分最小流量，判断是否可行
即 \(T\)->\(S\) 的边的流量为 \([0,x]\)

法二

1 . 先不连 \(T\)->\(S\) 流量为 \(inf\) 的边，求一次附加源到附加汇的最大流
2 . 再连上 \(T\)->\(S\) 流量为 \(inf\) 的边，在残量网络上求一次 \(s\) 到 \(t\) 的最大流
3 . 若最后满流，则答案为 \(T\)->\(S\) 的反向边的流量

因为第一遍做的时候并无这条边，所以 \(s\)->\(t\)的流量在第一遍做的时候都已经尽力往其他边流了.
于是加上 \(T\)->\(S\) 这条边后，都是些剩余的流不到其他边的流量. 从而达到尽可能减少 \(T\)->\(S\) 这边上的流量的效果，即减小了最终答案.

例1：BZOJ 1458

有一个 \(M \times N\) 的棋盘，有的格子可以放置士兵。要求第\(i\)行至少放置了 \(Li\) 个士兵, 第 \(j\) 列至少放置了 \(Cj\) 个士兵。求最少士兵数。

\(s\) 到每一行连 \([Li,inf]\) , 每一列到 \(t\) 连 \([Ci,inf]\) , 可以放士兵的行列连 \([0,1]\) . 

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
#include <iostream>
#include <cstdio>
#include <queue>
const int inf=0x7fffffff;
int n,m,K,s,t,S,T,ecnt=1,ans,du[205],ds[205],g[101][101];
int head[205],next[21000],to[21000],rest[21000];
std::queue<int> Q;
inline void Addedge(int x,int y,int r)
{
	to[++ecnt]=y;rest[ecnt]=r;next[ecnt]=head[x];head[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=0;next[ecnt]=head[y];head[y]=ecnt;
}
inline bool Bfs()
{
	for(int i=0;i<=T;i++) ds[i]=0;
	Q.push(S);ds[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int e=head[x],y=to[e];e;y=to[e=next[e]])
			if(rest[e]&&!ds[y])
				ds[y]=ds[x]+1,Q.push(y);
	}
	return ds[T];
}
inline int Maxflow(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(rest[e]&&ds[y]==ds[x]+1)
		{
			b=Maxflow(y,std::min(flow-a,rest[e]));
			a+=b;rest[e]-=b;rest[e^1]+=b;
			if(a==flow) break;
		}
	if(!a) ds[x]=0;
	return a;
}
int main()
{
	scanf("%d%d%d",&n,&m,&K);
	s=n+m+1;t=n+m+2;S=0;T=n+m+3;
	for(int i=1,x;i<=n;i++)
		scanf("%d",&x),Addedge(s,i,inf),du[s]-=x,du[i]+=x;
	for(int i=n+1,x;i<=n+m;i++)
		scanf("%d",&x),Addedge(i,t,inf),du[i]-=x,du[t]+=x;
	for(int i=1,x,y;i<=K;i++)
		scanf("%d%d",&x,&y),g[x][y]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!g[i][j])
				Addedge(i,n+j,1);
	for(int i=1;i<=t;i++)
		if(du[i]>0) Addedge(S,i,du[i]),ans+=du[i];
		else if(du[i]<0) Addedge(i,T,-du[i]);
	while(Bfs()) ans-=Maxflow(S,inf);
	Addedge(t,s,inf);
	while(Bfs()) ans-=Maxflow(S,inf);
	if(ans) printf("JIONG!");
	else printf("%d\n",rest[ecnt]);
}

例2：BZOJ 2502

滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。 每次可以使一个人降落到滑雪场的某个地点，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。求最少多少人才能完成清理雪道的任务。

\(s\) 向入度为 \(0\) 的点连 \([0,inf]\) , 出度为 \(0\) 的点向 \(t\) 连 \([0,inf]\) , 图上的每条边连 \([1,inf]\) .

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
#include <iostream>
#include <cstdio>
#include <queue>
const int inf=0x7fffffff;
int n,s,t,S,T,ecnt=1,in[105],out[105],ds[105];
int head[105],next[21000],to[21000],rest[21000];
std::queue<int> Q;
inline void Addedge(int x,int y,int r)
{
	to[++ecnt]=y;rest[ecnt]=r;next[ecnt]=head[x];head[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=0;next[ecnt]=head[y];head[y]=ecnt;
}
inline bool Bfs()
{
	for(int i=0;i<=T;i++) ds[i]=0;
	Q.push(S);ds[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int e=head[x],y=to[e];e;y=to[e=next[e]])
			if(rest[e]&&!ds[y])
				ds[y]=ds[x]+1,Q.push(y);
	}
	return ds[T];
}
inline int Maxflow(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(rest[e]&&ds[y]==ds[x]+1)
		{
			b=Maxflow(y,std::min(flow-a,rest[e]));
			a+=b;rest[e]-=b;rest[e^1]+=b;
			if(a==flow) break;
		}
	if(!a) ds[x]=0;
	return a;
}
int main()
{
	scanf("%d",&n);
	s=n+1;t=n+2;T=n+3;
	for(int i=1,x,j;i<=n;i++)
	{
		scanf("%d",&x);
		while(x--)
		{
			scanf("%d",&j);Addedge(i,j,inf);
			out[i]++;in[j]++;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!in[i]) Addedge(s,i,inf);
		if(!out[i]) Addedge(i,t,inf);
		if(in[i]>out[i]) Addedge(S,i,in[i]-out[i]);
			else Addedge(i,T,out[i]-in[i]);
	}
	while(Bfs()) Maxflow(S,inf);
	Addedge(t,s,inf);
	while(Bfs()) Maxflow(S,inf);
	printf("%d",rest[ecnt]);
}

参考：1 & 2 & 3

网络流 上下界网络流