上下界网络流

  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]\)

#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)\) 的限制

#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]\) 的边。

#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]\) .

#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]\) .

#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