上下界可行流问题描述的是,对于一个流网络,其边不仅有流量上界限制,还有流量下界限制,参考一般的可行流,我们可以作出如下定义:
在流网络中满足以下条件的网络流称为上下界可行流
-
容量限制 :
$\forall u,v\in V: c_下(u,v)\leq f(u,v)\leq c_上(u,v)$
($c_u$和$c_l$太像铜和氯,所以用上和下表示 -
流守恒 :
除了源点和汇点,所有点流出流量之和=流入流量之和
观察一下两者之间的差别,我们可以发现对于一个一般的可行流,我们可以把它看作是一个每条边的容量下界都为$0$的上下界可行流。
无源汇上下界可行流
建图
我们现在想把一个有上下界限制的流网络 $G=(E,V)$ 转化成一个只有上界限制的新流网络 $G’$ 。
网络 $G$ 需要满足每条边的流量都满足容量下界 $c_下(u,v)$ ,一种朴素的想法是我们先给每条边一个大小为下界的流量,看能否通过合理的调配这些流量使得流守恒。
如此,我们可以这么建图:
- 建立一个虚拟源点 $S$ ,向每个点连接一条容量为流入这个点容量下界之和的边,用来派发流量
- 建立一个虚拟汇点 $T$ ,每个点向汇点连接一条容量为流出这个点容量下界之和的边,用来接收流量
- 每条边的容量下界设为0,容量设为原本的上界减去原本的下界的容量
举个例子:
流出$S$的容量和等于流入$T$的容量和等于所有边的下界和,即
$$\sum_{u\in V} c(S,u)=\sum_{u\in V} c(u,T) $$
考虑一个点$u$,因为每一条终点为$u$边都必须满足容量下界,所以$S$向$u$流出的流量等于网络$G$中必须流入该点的流量,同理,$u$向$T$流出的流量等于$G$中$u$必须流出的流量。
对于$G’$和源汇不相连的边,每条边容量用多少都无所谓,可以看作调配流量的可用空间。
例如,对与上面的流网络,我们可以通过$S$向$1$节点流$3$单位的流量,对于$G$和$G’$分别是:
$1$号节点向$T$流出$1$单位的流量,表示需要满足的下界,剩下多余的流量流向$2$号,表示调用可用的容量来使流量平衡。
可以发现,对于 $G’$ 的每一条增广路 $p’$ ,都对应 $G$ 的一个流量调配的可行方案(路径)$p$
网络$G$每条边都需要满足流量下界的限制,所以当且仅当$G’$中$S$的出边都达到满流,$T$的入边也都达到满流时,$G$存在可行流。
当一个点$u$同时有和$S,T$相连的边时,因为有$\min(c(S,u),c(u,T))$的流量可以直接通过$S\rightarrow u \rightarrow T$的路线解决,所以可以去除一条边得到一个等价的网络,以此来减少边的数量。
总结一下最后的建图方式就是:
- 建立虚拟的源汇点,对于任意一点 $u\in E$ ,当$x=\sum c_下(v,u)-\sum c_下(u,v)>0$ 时,从源点向$u$连一条容量为$x$的边,反之从$u$向汇点连接一条容量为$-x$的边
- 原网络中的每条边的容量设为为$c_上(u,v)-c_下(u,v)$
对新网络$G’$跑最大流算法即得解。
新网络边的流量加上原本的下界容量就是原网络的一个方案。
实现
inline void add(int a,int b,int c,int d){
e[idx]=b,f[idx]=d-c,l[idx]=c,ne[idx]=h[a],h[a]=idx++;
e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
int dinic(){
int F=0,flow;
while(bfs()) while(flow=dfs(S,INF)) F+=flow;
return F;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
memset(h,-1,sizeof h);
cin>>n>>m;
S=0,T=n+1;
while(m--){
int a,b,c,d;
cin>>a>>b>>c>>d;
add(a,b,c,d);
sum[a]-=c,sum[b]+=c;
}
int total=0;
for(int i=1;i<=n;i++){
if(sum[i]>0) add(S,i,0,sum[i]) ,total+=sum[i];
else if(sum[i]<0) add(i,T,0,-sum[i]);
}
if(dinic()<total) cout<<"NO";
else{
cout<<"YES"<<endl;
for(int i=0;i<idx;i+=2)
if(e[i]<=n&&e[i^1]) cout<<f[i^1]+l[i]<<endl;
}
return 0;
}
有源汇上下界可行流
对于原本就有源汇点的上下界可行流问题,我们可以把它转化为无源汇的形式解决。
$S,T$可以看作两个特殊点,它们不满足流守恒。我们可以简单的建一条$T\rightarrow S$,容量下界为0,上界为$\infty$的边使它们能够流守恒,这样就转化为了一个无源汇的上下界可行流问题。
有源汇上下界最大流
和有源汇可行流类似,求上下界流网络的最大流
观察下面的网络,可以发现在网络已经满足下界条件且流守恒的情况下,$s\rightarrow t$ 可以流更多的流量。
由于在做完一遍无源汇上下界可行流时,和 $S,T$ 相连的边都已经满流,所以$s\rightarrow t$ 的增广路上一定不包含$S,T$,所以我们不必拆除$S,T$和与其相连的边,因为它们不影响结果,从$s$到$t$求一遍最大流再加上原本的可行流流量即可。注意求最大流的时候要拆掉新加的 $t\rightarrow s$ 的边,否则答案可能会偏大。
实现
int main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
memset(h,-1,sizeof h);
int s,t;
cin>>n>>m>>s>>t;
S=0,T=n+1;
while(m--){
int a,b,c,d;
cin>>a>>b>>c>>d;
add(a,b,d-c);
sum[b]+=c,sum[a]-=c;
}
int total=0;
for(int i=1;i<=n;i++){
if(sum[i]>0) add(S,i,sum[i]),total+=sum[i];
else if(sum[i]<0) add(i,T,-sum[i]);
}
add(t,s,INF);
if(dinic()<total) cout<<"No Solution";
else {
int res=f[idx-1];
f[idx-1]=f[idx-2]=0;
S=s,T=t;
cout<<res+dinic();
}
return 0;
}
有源汇上下界最小流
和最大流类似,从$s$到$t$的流量表示剩下还可以追加的流量,在求最小流的时候,我们反向搜索从$t$到$s$的最大流,表示可以从可行流中退回的部分流量。注意同样要删去额外加上的$t\rightarrow s$的边,否则会退回无穷大的流量。