上下界网络流学习笔记
无源汇有上下界可行流
模型
(n) 个点，(m) 条边，每条边有一个流量下界和流量上界，求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。
做法
如果存在一个可行流，那么所有边的流量一定是大于等于流量下界的，
所以我们可以在一开始把所有边的流量都减去流量下界，
剩余的残量网络中每条边的流量就是原图中的每条边的流量上界减去流量下界。
但是因为我们人为地减去了一些流量，所以每一个点不一定满足流量守恒。
比如说原图中有一条从 (a) 到 (b)，流量下界为 (x) 的边，我们把它的流量变成了 (0)。
但是实际上我们是想让它至少流出 (x) 的流量的，要给这些流量找一个去的地方，就要新建一个超级汇点 (t)，由这个点向超级汇点连一条流量为 (x) 的边。
同理，对于 (b) ，我们想让它至少流入 (x) 的流量，要给这些流量找一个来的地方，就要新建一个超级源点 (s)，由超级源点向这个点连一条流量为 (x) 的边。
直接在新建的图上跑网络流即可。
每条边实际的流量就是之前减去的流量下界加上新增广出的流量。
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=2e4+5;
int h[maxn],tot=2,n,m,s,t,h2[maxn];
struct asd{
int to,nxt,val,num;
}b[maxn<<1];
void ad(rg int aa,rg int bb,rg int cc,rg int dd){
b[tot].to=bb;
b[tot].nxt=h[aa];
b[tot].val=cc;
b[tot].num=dd;
h[aa]=tot++;
}
int dep[maxn],q[maxn],head,tail;
bool bfs(){
for(rg int i=1;i<=t;i++){
h[i]=h2[i];
dep[i]=0;
}
q[head=tail=1]=s;
dep[s]=1;
while(head<=tail){
rg int now=q[head++];
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(b[i].val && !dep[u]){
dep[u]=dep[now]+1;
q[++tail]=u;
}
}
}
return dep[t]!=0;
}
int dfs(rg int now,rg int ac1){
if(now==t) return ac1;
rg int ac2=0;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
h[now]=i;
rg int u=b[i].to;
if(dep[u]==dep[now]+1 && b[i].val){
rg int nans=dfs(u,std::min(b[i].val,ac1));
b[i].val-=nans;
b[i^1].val+=nans;
ac1-=nans;
ac2+=nans;
}
if(ac1==0) break;
}
if(!ac2) dep[now]=0;
return ac2;
}
int low[maxn],up[maxn],totflow[maxn],sum,ans[maxn],nans;
int main(){
memset(h,-1,sizeof(h));
n=read(),m=read();
rg int aa,bb;
for(rg int i=1;i<=m;i++){
aa=read(),bb=read(),low[i]=read(),up[i]=read();
ad(aa,bb,up[i]-low[i],i);
ad(bb,aa,0,i);
totflow[aa]-=low[i],totflow[bb]+=low[i];
}
s=n+1,t=n+2;
for(rg int i=1;i<=n;i++){
if(totflow[i]<0){
ad(i,t,-totflow[i],0);
ad(t,i,0,0);
} else {
sum+=totflow[i];
ad(s,i,totflow[i],0);
ad(i,s,0,0);
}
}
for(rg int i=1;i<=t;i++) h2[i]=h[i];
while(bfs()) nans+=dfs(s,0x3f3f3f3f);
if(nans==sum){
printf("YES
");
for(rg int i=1;i<=t;i++){
for(rg int j=h[i];j!=-1;j=b[j].nxt){
if(j%2==0 || !b[j].num) continue;
ans[b[j].num]=b[j].val+low[b[j].num];
}
}
for(rg int i=1;i<=m;i++) printf("%d
",ans[i]);
} else {
printf("NO
");
}
return 0;
}
有源汇有上下界可行流
模型
(n) 个点，(m) 条边，每条边有一个流量下界和流量上界 ，给定源点与汇点 ，求源点到汇点的可行流。
做法
由汇点 (tt) 向 源点 (ss) 连一条流量下界为 (0)，上界为无穷大的边，就可以转化为无源汇有上下界可行流的模型。
最终得到的可行的有源汇流的流量就是 (tt) 到 (ss) 反向边的流量。
有源汇有上下界最小流
模型
(n) 个点，(m) 条边，每条边有一个流量下界和流量上界 ，给定源点与汇点 ，求源点到汇点的最小流。
做法
先跑一遍有源汇有上下界可行流，然后把 (ss) 到 (tt) 的边断掉，以 (tt) 为起点 (ss) 为终点进行流量的增广，最终的答案就是可行流的流量减去新增广出的流量。
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=2e5+5;
int h[maxn],tot=2,n,m,s,t,h2[maxn],ss,tt,mmax;
struct asd{
int to,nxt,val,num;
}b[maxn<<1];
void ad(rg int aa,rg int bb,rg int cc,rg int dd){
b[tot].to=bb;
b[tot].nxt=h[aa];
b[tot].val=cc;
b[tot].num=dd;
h[aa]=tot++;
}
int dep[maxn],q[maxn],head,tail;
bool bfs(){
for(rg int i=1;i<=mmax;i++){
h[i]=h2[i];
dep[i]=0;
}
q[head=tail=1]=s;
dep[s]=1;
while(head<=tail){
rg int now=q[head++];
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(b[i].val && !dep[u]){
dep[u]=dep[now]+1;
q[++tail]=u;
}
}
}
return dep[t]!=0;
}
int dfs(rg int now,rg int ac1){
if(now==t) return ac1;
rg int ac2=0;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
h[now]=i;
rg int u=b[i].to;
if(dep[u]==dep[now]+1 && b[i].val){
rg int nans=dfs(u,std::min(b[i].val,ac1));
b[i].val-=nans;
b[i^1].val+=nans;
ac1-=nans;
ac2+=nans;
}
if(ac1==0) break;
}
if(!ac2) dep[now]=0;
return ac2;
}
int low[maxn],up[maxn],totflow[maxn],sum,nans,tmp;
int main(){
memset(h,-1,sizeof(h));
n=read(),m=read(),ss=read(),tt=read();
rg int aa,bb;
s=n+1,t=n+2,mmax=n+2;
for(rg int i=1;i<=m;i++){
aa=read(),bb=read(),low[i]=read(),up[i]=read();
ad(aa,bb,up[i]-low[i],i);
ad(bb,aa,0,i);
totflow[aa]-=low[i],totflow[bb]+=low[i];
}
tmp=tot;
ad(tt,ss,0x3f3f3f3f,m+1);
ad(ss,tt,0,m+1);
for(rg int i=1;i<=n;i++){
if(totflow[i]<0){
ad(i,t,-totflow[i],0);
ad(t,i,0,0);
} else {
sum+=totflow[i];
ad(s,i,totflow[i],0);
ad(i,s,0,0);
}
}
for(rg int i=1;i<=mmax;i++) h2[i]=h[i];
while(bfs()) nans+=dfs(s,0x3f3f3f3f);
if(nans==sum){
nans=b[tmp^1].val;
b[tmp].val=b[tmp^1].val=0;
s=tt,t=ss;
while(bfs()) nans-=dfs(s,0x3f3f3f3f);
printf("%d
",nans);
} else {
printf("please go home to sleep
");
}
return 0;
}
有源汇有上下界最大流
模型
(n) 个点，(m) 条边，每条边有一个流量下界和流量上界 ，给定源点与汇点 ，求源点到汇点的最大流。
做法
先跑一遍有源汇有上下界可行流，然后把 (ss) 到 (tt) 的边断掉，以 (ss) 为起点 (tt) 为终点进行流量的增广，最终的答案就是可行流的流量加上新增广出的流量。
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=2e4+5;
int h[maxn],tot=2,n,m,s,t,h2[maxn],ss,tt,mmax;
struct asd{
int to,nxt,val,num;
}b[maxn<<1];
void ad(rg int aa,rg int bb,rg int cc,rg int dd){
b[tot].to=bb;
b[tot].nxt=h[aa];
b[tot].val=cc;
b[tot].num=dd;
h[aa]=tot++;
}
int dep[maxn],q[maxn],head,tail;
bool bfs(){
for(rg int i=1;i<=mmax;i++){
h[i]=h2[i];
dep[i]=0;
}
q[head=tail=1]=s;
dep[s]=1;
while(head<=tail){
rg int now=q[head++];
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(b[i].val && !dep[u]){
dep[u]=dep[now]+1;
q[++tail]=u;
}
}
}
return dep[t]!=0;
}
int dfs(rg int now,rg int ac1){
if(now==t) return ac1;
rg int ac2=0;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
h[now]=i;
rg int u=b[i].to;
if(dep[u]==dep[now]+1 && b[i].val){
rg int nans=dfs(u,std::min(b[i].val,ac1));
b[i].val-=nans;
b[i^1].val+=nans;
ac1-=nans;
ac2+=nans;
}
if(ac1==0) break;
}
if(!ac2) dep[now]=0;
return ac2;
}
int low[maxn],up[maxn],totflow[maxn],sum,nans;
int main(){
memset(h,-1,sizeof(h));
n=read(),m=read(),ss=read(),tt=read();
rg int aa,bb;
s=n+1,t=n+2,mmax=n+2;
for(rg int i=1;i<=m;i++){
aa=read(),bb=read(),low[i]=read(),up[i]=read();
ad(aa,bb,up[i]-low[i],i);
ad(bb,aa,0,i);
totflow[aa]-=low[i],totflow[bb]+=low[i];
}
ad(tt,ss,0x3f3f3f3f,m+1);
ad(ss,tt,0,m+1);
for(rg int i=1;i<=n;i++){
if(totflow[i]<0){
ad(i,t,-totflow[i],0);
ad(t,i,0,0);
} else {
sum+=totflow[i];
ad(s,i,totflow[i],0);
ad(i,s,0,0);
}
}
for(rg int i=1;i<=mmax;i++) h2[i]=h[i];
while(bfs()) nans+=dfs(s,0x3f3f3f3f);
if(nans==sum){
for(rg int i=1;i<tot;i++){
if(b[i].num==m+1 && i&1) nans=b[i].val;
if(b[i].num==m+1) b[i].val=0;
}
s=ss,t=tt;
while(bfs()) nans+=dfs(s,0x3f3f3f3f);
printf("%d
",nans);
} else {
printf("please go home to sleep
");
}
return 0;
}