上下界网络流

  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的特殊情况

无源汇

可行流

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

法一

即对于一条边 (u,v)(u,v) ,在图中建三条边 (u,v,highlow),(S,v,low),(u,T,low)(u,v,high-low) , (S,v,low) , (u,T,low)

法二

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

例:sgu 194

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

1.建立原图中的边,(u,v,highlow)(u,v,high-low)du[u]=low,du[v]+=lowdu[u]-=low , du[v]+=low
2.对于每个点i,如果 du[i]>0du[i] > 0,建边(S,i,du[i]) (S,i,du[i]) ,否则建边(i,T,du[i]) (i,T,-du[i])
3.如果maxflow(S,T)==du[i]>0du[i] 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]);
}
}

有源汇

可行流

TTSS 连一条 [0,inf][0,inf] 的边,有源汇就变成了无源汇,就和上面一样了

例:POJ 2396

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

对于每行和每列分别建一个点,ss 与每行的点连 [a[i],a[i]][a[i],a[i]] 的边,每列的点与 tt[b[i],b[i]][b[i],b[i]] 的边,中间连的边为点(i,j)(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");
}
}

最大流

法一

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

法二

1 . 连上 TT->SS 流量为 infinf 的边,求一次附加源到附加汇的最大流,若不满流则无解
2 . 在残量网络上求一次 sstt 的最大流
3 . 答案就是第二次求出的最大流(因为第一次求出的最大流是 TT->SS 的流量,而这个流量在他的反向边 ss->tt 中出现,所以不需要另外加上)

第一次求出的最大流是为了满足 lowlow 尽可能流满,然而此时 ss->tt 上可能还有可行的流,我们在残量网络上继续来求最大流,可以使得最后求出的流既满足 的限制,且最大。

例:ZOJ 3229

一个人给 mm 个女神拍照,计划拍照 nn 天,每天拍照数不能超过 DiDi 张,而且给每个女神 ii 拍照有数量限制 [Li,Ri][Li,Ri],对于每个女神n天的拍照总和不能超过 GiGi,如果有解最多能拍多少张照,并求每天给对应女神拍多少张照;否则输出 1-1

ss 到第 ii 天连接 [0,Di][0,Di] 的边,第 ii 个女神到 tt 连接 [Gi,inf][Gi,inf] 的边 ; 对于每一天,当天到第 ii 个女神连一条 [Li,Ri][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");
}
}

最小流

法一

二分最小流量,判断是否可行
TT->SS 的边的流量为 [0,x][0,x]

法二

1 . 先不连 TT->SS 流量为 infinf 的边,求一次附加源到附加汇的最大流
2 . 再连上 TT->SS 流量为 infinf 的边,在残量网络上求一次 sstt 的最大流
3 . 若最后满流,则答案为 TT->SS 的反向边的流量

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

例1:BZOJ 1458

有一个 M×NM \times N 的棋盘,有的格子可以放置士兵。要求第ii行至少放置了 LiLi 个士兵, 第 jj 列至少放置了 CjCj 个士兵。求最少士兵数。

ss 到每一行连 [Li,inf][Li,inf] , 每一列到 tt[Ci,inf][Ci,inf] , 可以放士兵的行列连 [0,1][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

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

ss 向入度为 00 的点连 [0,inf][0,inf] , 出度为 00 的点向 tt[0,inf][0,inf] , 图上的每条边连 [1,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