最近在做网络流。前些日子在$CDQZ$集训的时候看了看，现在来做做题。
大力推荐一发liu_runda的博客！写的太好了（其实也是我懒得写学习笔记）。
简单写几句要点吧2333
1.无源汇有上下界可行流(也就是循环流)
先以下界构图，再在残余网络中通过构建虚拟源汇调整流量，使得满足各个点流入量=流出量
每条边流量=下界+残余网络中跑出的流量
例题：[ZOJ 2314]Reactor Cooling
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cmath>
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 510000
const int inf=0x7fffffff;
int anti(int x){return (x&1)?(x+1):(x-1);}
char xB[(1<<15)+10],*xS=xB,*xT=xB;
#define gtc (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline void read(int &shu){
register char ch=gtc;int f=1;
for(shu=0;ch<'0'||ch>'9';ch=gtc)if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';shu=(shu<<1)+(shu<<3)+ch-'0',ch=gtc);
shu*=f;
}
int n,m,T;
int up[N],down[N],tot[N];
struct haha{
int next,to,w;
}edge[N];
int head[N],cnt,s,t,sum;
void add(int u,int v,int w){
edge[++cnt].w=w;
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
int dep[N];
bool bfs(){
memset(dep,0,sizeof(dep));
dep[s]=1;std::queue<int> q;
q.push(s);
while(!q.empty()){
int k=q.front();q.pop();
for(int i=head[k];i;i=edge[i].next){
int to=edge[i].to,w=edge[i].w;
if(!dep[to]&&w){
dep[to]=dep[k]+1;
if(to==t) return 1;
q.push(to);
}
}
}
return 0;
}
int dfs(int x,int f){
if(x==t) return f;
int temp=f;
for(int i=head[x];i;i=edge[i].next){
int to=edge[i].to,w=edge[i].w;
if(temp&&dep[to]==dep[x]+1&&w){
int k=dfs(to,std::min(temp,w));
if(!k){dep[to]=0;continue;}
temp-=k;edge[i].w-=k;edge[anti(i)].w+=k;
}
}
return f-temp;
}
void work(){
int res(0);
while(bfs()) res+=dfs(s,inf);
if(res==sum){
printf("YES\n");
pos(i,1,m){
printf("%d\n",down[i]+edge[i*2].w);
}
}
else printf("NO\n");
}
void init(){
memset(edge,0,sizeof(edge));
cnt=sum=0;s=n+1;t=s+1;
pos(i,0,N-10) tot[i]=head[i]=up[i]=down[i]=0;
}
int main(){
read(T);
while(T--){
read(n);read(m);
init();
pos(i,1,m){
int x,y;read(x);read(y);read(down[i]);read(up[i]);
add(x,y,up[i]-down[i]);add(y,x,0);
tot[y]+=down[i];tot[x]-=down[i];
}
pos(i,1,n){
if(tot[i]>0) add(s,i,tot[i]),add(i,s,0),sum+=tot[i];
else add(i,t,-tot[i]),add(t,i,0);
}
work();
}
return 0;
}
2.有源汇有上下界可行流
建$t$->$s$的边，形成无源汇的图，再跑无源汇上下界可行流，最后删去此边即可
原图中可行流的总流量=此边在无源汇图中跑出的流量
每条边流量=下界+残余网络中跑出的流量
3.有源汇有上下界最大流
跑完有源汇有上下界可行流后，按每条边剩下的流量重构原图，再跑最大流，这样保证可行同时流最大
原图中最大流总流量=可行流总流量+最大流总流量
每条边流量=下界+残余网络中跑出的流量+重构图中跑出的流量
例题：[ZOJ 3229]Shoot the Bullet
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 2010
const int inf=0x7ffffff;
int anti(int x){return (x&1)?(x+1):(x-1);}
int n,m;
int up[610000],down[600000],tot[N],sz,sz2;
struct haha{
int next,to,w;
}edge[2][600000];
int head[2][N],cnt[2],s[2],t[2];
int ss,tt,sum,cun[600000],ge[1000][1000];
int hmin(int x,int y){return x>y?y:x;}
void add(int u,int v,int w,int k){
edge[k][++cnt[k]].w=w;
edge[k][cnt[k]].to=v;
edge[k][cnt[k]].next=head[k][u];
head[k][u]=cnt[k];
}
int dep[N];
bool bfs(int k){
memset(dep,0,sizeof(dep));
dep[s[k]]=1;
std::queue<int> q;q.push(s[k]);
while(!q.empty()){
int kk=q.front();q.pop();
for(int i=head[k][kk];i;i=edge[k][i].next){
int to=edge[k][i].to,w=edge[k][i].w;
if(!dep[to]&&w){
dep[to]=dep[kk]+1;
if(to==t[k]) return 1;
q.push(to);
}
}
}
return 0;
}
int dfs(int x,int f,int k){
if(x==t[k]) return f;
int temp=f;
for(int i=head[k][x];i;i=edge[k][i].next){
int to=edge[k][i].to,w=edge[k][i].w;
if(temp&&dep[to]==dep[x]+1&&w){
int kk=dfs(to,hmin(temp,w),k);
if(!kk){dep[to]=0;continue;}
temp-=kk;edge[k][i].w-=kk;edge[k][anti(i)].w+=kk;
}
}
return f-temp;
}
int ans1;
void work(){
int res(0);
while(bfs(0)) res+=dfs(s[0],inf,0);
if(res==sum){
ans1=edge[0][sz*2].w;
pos(i,1,m){
++sz2;
add(n+i,t[1],up[sz2]-down[sz2]-edge[0][sz2*2].w,1);add(t[1],n+i,0,1);
}
pos(i,1,n){
++sz2;
add(s[1],i,up[sz2]-down[sz2]-edge[0][sz2*2].w,1);add(i,s[1],0,1);
pos(j,1,ge[i][0]){
++sz2;
add(i,n+ge[i][j],up[sz2]-down[sz2]-edge[0][sz2*2].w,1);add(n+ge[i][j],i,0,1);
}
}
while(bfs(1)) ans1+=dfs(s[1],inf,1);
printf("%d\n",ans1);
pos(i,1,cun[0]){
printf("%d\n",edge[0][cun[i]*2].w+edge[1][cun[i]*2].w+down[cun[i]]);
}
}
else printf("-1\n");
}
void init(){
memset(edge,0,sizeof(edge));
memset(head,0,sizeof(head));
cnt[0]=cnt[1]=sz=sz2=sum=cun[0]=ans1=0;
pos(i,0,N-10) tot[i]=0;
}
signed main(){
while(scanf("%d%d",&n,&m)!=EOF){
init();
ss=n+m+1;tt=ss+2;
s[0]=s[1]=tt+1;t[0]=t[1]=tt+2;
pos(i,1,m){
++sz;scanf("%d",&down[sz]);up[sz]=inf;
add(n+i,tt,up[sz]-down[sz],0);add(tt,n+i,0,0);
tot[tt]+=down[sz];tot[n+i]-=down[sz];
}
pos(i,1,n){
scanf("%d",&ge[i][0]);
++sz;scanf("%d",&up[sz]);down[sz]=0;
add(ss,i,up[sz]-down[sz],0);add(i,ss,0,0);
tot[i]+=down[sz];tot[ss]-=down[sz];
pos(j,1,ge[i][0]){
++sz;cun[++cun[0]]=sz;
scanf("%d%d%d",&ge[i][j],&down[sz],&up[sz]);
ge[i][j]++;
add(i,n+ge[i][j],up[sz]-down[sz],0);add(n+ge[i][j],i,0,0);
tot[n+ge[i][j]]+=down[sz];tot[i]-=down[sz];
}
}
++sz;add(tt,ss,inf,0);add(ss,tt,0,0);up[sz]=inf;down[sz]=0;
pos(i,1,tt){
if(tot[i]>0) add(s[0],i,tot[i],0),add(i,s[0],0,0),sum+=tot[i];
else add(i,t[0],-tot[i],0),add(t[0],i,0,0);
}
work();
printf("\n");
}
return 0;
}
4.有源汇有上下界最小流
跑完有源汇有上下界可行流后，按跑出的残余流量图重构原图，再从$t$->$s$跑最大流，由于反边存的是跑过的流量，这样可以最大“退回”跑过的流量
原图中最小流总流量=可行流总流量-反向跑出最大流总流量
每条边流量=下界+残余网络中跑出的流量-反向跑出的流量
例题：[BZOJ 2502]清理雪道
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 201000
const int inf=0x3fffffff;
int anti(int x){return (x&1)?(x+1):(x-1);}
char xB[(1<<15)+10],*xS=xB,*xT=xB;
#define gtc (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline void read(int &shu){
register char ch=gtc;int f=1;
for(shu=0;ch<'0'||ch>'9';ch=gtc) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';shu=(shu<<1)+(shu<<3)+ch-'0',ch=gtc);
shu*=f;
}
int n;
struct haha{
int next,to,w;
}edge[2][N];
int head[2][N],cnt[2];
void add(int u,int v,int w,int k){
edge[k][++cnt[k]].w=w;edge[k][cnt[k]].to=v;
edge[k][cnt[k]].next=head[k][u];head[k][u]=cnt[k];
}
int s,t,ss,tt;
int sz,sz2,up[N],down[N],sum;
int ge[500][500];
int ans,dep[N];
bool bfs(int k,int s1,int t1){
std::queue<int> q;q.push(s1);
memset(dep,0,sizeof(dep));
dep[s1]=1;
while(!q.empty()){
int kk=q.front();q.pop();
for(int i=head[k][kk];i;i=edge[k][i].next){
int to=edge[k][i].to,w=edge[k][i].w;
if(!dep[to]&&w){
dep[to]=dep[kk]+1;
if(to==t1) return 1;
q.push(to);
}
}
}
return 0;
}
int dfs(int x,int t1,int f,int k){
if(x==t1) return f;
int temp=f;
for(int i=head[k][x];i;i=edge[k][i].next){
int to=edge[k][i].to,w=edge[k][i].w;
if(w&&temp&&dep[to]==dep[x]+1){
int kk=dfs(to,t1,std::min(temp,w),k);
if(!kk){
dep[to]=0;continue;
}
temp-=kk;edge[k][i].w-=kk;edge[k][anti(i)].w+=kk;
}
}
return f-temp;
}
int tot[N];
void work(){
int res(0);
while(bfs(0,ss,tt)) res+=dfs(ss,tt,inf,0);
ans+=edge[0][sz*2].w;
pos(i,1,n){
++sz2;add(s,i,edge[0][sz2*2-1].w,1);add(i,s,edge[0][sz2*2].w,1);
++sz2;add(i,t,edge[0][sz2*2-1].w,1);add(t,i,edge[0][sz2*2].w,1);
}
pos(i,1,n){
pos(j,1,ge[i][0]){
++sz2;add(i,ge[i][j],edge[0][sz2*2-1].w,1);add(ge[i][j],i,edge[0][sz2*2].w,1);
}
}
while(bfs(1,t,s)) ans-=dfs(t,s,inf,1);
printf("%d\n",ans);
}
int main(){
read(n);s=n+1;t=s+1;ss=t+1;tt=ss+1;
pos(i,1,n){
++sz;up[sz]=inf;add(s,i,inf,0);add(i,s,0,0);
++sz;up[sz]=inf;add(i,t,inf,0);add(t,i,0,0);
}
pos(i,1,n){
read(ge[i][0]);
pos(j,1,ge[i][0]){
read(ge[i][j]);
++sz;up[sz]=inf;down[sz]=1;add(i,ge[i][j],up[sz]-down[sz],0);add(ge[i][j],i,0,0);
tot[ge[i][j]]+=down[sz];tot[i]-=down[sz];
}
}
++sz;up[sz]=inf;add(t,s,inf,0);add(s,t,0,0);
pos(i,1,t){
if(tot[i]>0) add(ss,i,tot[i],0),add(i,ss,0,0);
else if(tot[i]<0) add(i,tt,-tot[i],0),add(tt,i,0,0);
}
work();
return 0;
}
5.有源汇有上下界最小费用可行流
在跑可行流的时候，因为跑满流即存在可行解，而满流方案有很多种，我们要求的是[可行]->[最小费用]，所以跑最小费用最大流即可
最小费用=有费用的边*容量下界+跑出来的最小费用
例题：[BZOJ 2055]80人环游世界
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 101000
const int inf=0x7f7f7f7f;
int anti(int x){return (x&1)?(x+1):(x-1);}
char xB[(1<<15)+10],*xS=xB,*xT=xB;
#define gtc (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline void read(int &shu){
register char ch=gtc;int f=1;
for(shu=0;ch<'0'||ch>'9';ch=gtc) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';shu=(shu<<1)+(shu<<3)+ch-'0',ch=gtc);
shu*=f;
}
int n,m,ss,tt,s,t,pre;
int V[N],tot[N],up[N],down[N];
int sz,C[500][500];
struct haha{
int next,to,w,c;
}edge[N];
int head[N],cnt;
void add(int u,int v,int w,int c){
edge[++cnt].w=w;edge[cnt].to=v;
edge[cnt].c=c;edge[cnt].next=head[u];
head[u]=cnt;
}
int dis[N],flag[N],from[N];
int spfa(){
pos(i,0,N-10) dis[i]=inf,flag[i]=from[i]=0;
std::queue<int> q;dis[ss]=0;flag[ss]=1;q.push(ss);
while(!q.empty()){
int k=q.front();q.pop();
for(int i=head[k];i;i=edge[i].next){
int to=edge[i].to,w=edge[i].w,c=edge[i].c;
if(w&&dis[to]>dis[k]+c){
dis[to]=dis[k]+c;
if(!flag[to]){flag[to]=1;q.push(to);}
from[to]=i;
}
}
flag[k]=0;
}
return dis[tt]==inf?(-1):dis[tt];
}
int cost(){
int p=tt,f=inf;
while(p!=ss){
f=std::min(f,edge[from[p]].w);
p=edge[anti(from[p])].to;
}
p=tt;
while(p!=ss){
edge[from[p]].w-=f;
edge[anti(from[p])].w+=f;
p=edge[anti(from[p])].to;
}
return f;
}
void work(){
int res(0),l;
while(1){
l=spfa();if(l==-1) break;
res+=l*cost();
}
printf("%d\n",res);
}
int main(){
read(n);read(m);
s=n*2+1,t=s+1;pre=t+1;ss=pre+1;tt=ss+1;
pos(i,1,n){
read(V[i]);
++sz;up[sz]=V[i];down[sz]=V[i];
add(i,n+i,0,0);add(n+i,i,0,0);
tot[n+i]+=down[sz];tot[i]-=down[sz];
++sz;up[sz]=inf;
add(pre,i,inf,0);add(i,pre,0,0);
++sz;up[sz]=inf;
add(n+i,t,inf,0);add(t,n+i,0,0);
}
pos(i,1,n){
pos(j,i+1,n){
read(C[i][j]);if(C[i][j]==-1) continue;
++sz;up[sz]=inf;
add(n+i,j,inf,C[i][j]);add(j,n+i,0,-C[i][j]);
}
}
++sz;up[sz]=m;down[sz]=m;
add(s,pre,0,0);add(pre,s,0,0);
tot[pre]+=down[sz];tot[s]-=down[sz];
++sz;up[sz]=inf;
add(t,s,inf,0);add(s,t,0,0);
pos(i,1,pre){
if(tot[i]>0) add(ss,i,tot[i],0),add(i,ss,0,0);
else add(i,tt,-tot[i],0),add(tt,i,0,0);
}
work();
return 0;
}
--------------------------------以下部分仅为YY而来，并没有打题验证OvO----------------------------------
6.有源汇有上下界最X费用最X流
由于要满足[最X流]->[最X费用]，所以我们先按最X费用跑出可行流，再满足最X流且最X费用
掌握一个原则：最大流要尽量多跑，最小流要尽量多“退回”，所以参照上面的方法重构图或者反向跑即可
例如：最大费用最小流
由于要最小流，我们先跑最大费用最大流使得满流达到可行的效果，然后反向跑最小费用最大流，使得尽量多“退回”流的同时尽量少“退回”费用
其他类比即可OvO
![[知识点]有上下界的网络流学习笔记](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9pbWdzLzUvMS85LzgvMTcvMDA0NGQ4NzcyMzdmYzY2YWEzMmM3ODM0OGMwODgyZTcuanBl.jpe?w=700&webp=1 "[知识点]有上下界的网络流学习笔记")