各种形式
普通网络流
Dinic
#include<bits/stdc++.h>
using namespace std;
int n,tot=1,first[210],nnext[10010],to[10010],w[10010],que[210],src,des,lev[210],cur[210];
void add(int x,int y,int z){
nnext[++tot]=first[x];
first[x]=tot;
to[tot]=y;
w[tot]=z;
}
int bfs(){
int q=1,u;
memset(que,0,sizeof(que));
for(int i=1;i<=n;i++){
lev[i]=-1;
cur[i]=first[i];
}
que[1]=src;
lev[src]=0;
for(int l=1;l<=q;l++){
u=que[l];
for(int e=first[u];e;e=nnext[e]){
if(w[e]>0&&lev[to[e]]==-1){
lev[to[e]]=lev[u]+1;
que[++q]=to[e];
if(to[e]==des){
return 1;
}
}
}
}
return 0;
}
int dinic(int u,int flow){
int res=0,delta;
if(u==des){
return flow;
}
for(int &e=cur[u];e;e=nnext[e]){
if(w[e]>0&&lev[u]<lev[to[e]]){
delta=dinic(to[e],min(w[e],flow-res));
if(delta){
w[e]-=delta;
w[e^1]+=delta;
res+=delta;
if(res==flow){
break;
}
}
}
}
if(res!=flow){
lev[u]=-1;
}
return res;
}
int main(){
int a,b,c,m;
long long ans=0;
scanf("%d%d%d%d",&n,&m,&src,&des);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,0);
}
while(bfs()){
ans+=dinic(src,1e9);
}
printf("%lld",ans);
}
费用流
Dinic+SPFA
#include<bits/stdc++.h>
using namespace std;
int n,tot=1,first[500010],nnext[1000010],to[1000010],w[1000010],que[50010],src,des,cur[50010],dis[50010],vis[50010],cost[1000010];
long long sum;
void add(int x,int y,int z,int r){
nnext[++tot]=first[x];
first[x]=tot;
to[tot]=y;
w[tot]=z;
cost[tot]=r;
}
int bfs(){
int q=1,u;
memset(que,0,sizeof(que));
for(int i=1;i<=n;i++){
if(i==src){
dis[i]=0;
vis[i]=0;
continue;
}
dis[i]=1e9;
vis[i]=0;
}
que[1]=src;
for(int l=1;l<=q;l++){
u=que[l];
vis[u]=0;
for(int e=first[u];e;e=nnext[e]){
if(w[e]&&dis[u]+cost[e]<dis[to[e]]){
dis[to[e]]=dis[u]+cost[e];
if(vis[to[e]]==0){
que[++q]=to[e];
vis[to[e]]=1;
}
}
}
}
if(dis[des]==1e9){
return 0;
}
for(int i=1;i<=n;i++){
if(dis[i]!=1e9){
cur[i]=first[i];
vis[i]=0;
}
}
return 1;
}
int dinic(int u,int flow){
int res=0,delta;
if(u==des){
sum+=dis[des]*flow;
return flow;
}
vis[u]=1;
for(int &e=cur[u];e;e=nnext[e]){
if(w[e]>0&&vis[to[e]]==0&&dis[u]+cost[e]==dis[to[e]]){
delta=dinic(to[e],min(w[e],flow-res));
if(delta){
w[e]-=delta;
w[e^1]+=delta;
res+=delta;
if(res==flow){
break;
}
}
}
}
if(res==flow){
vis[u]=0;
}
return res;
}
int main(){
int a,b,c,d,m;
long long ans=0;
scanf("%d%d%d%d",&n,&m,&src,&des);
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&a,&b,&c,&d);
add(a,b,c,d);
add(b,a,0,-d);
}
while(bfs()){
ans+=dinic(src,1e9);
}
printf("%lld %lld",ans,sum);
}
无源汇有上下界可行流
先强制流下界，然后建超级源汇分别向流入大于流出和流出大于流入的连边。看是否满流。
#include<bits/stdc++.h>
using namespace std;
int tot=1,src,des,minu,maxu,first[210],nnext[21010],to[21010],cur[210],lev[210],d[210],w[21010],c[10210];
queue<int>q;
void add(int x,int y,int z){
nnext[++tot]=first[x];
first[x]=tot;
to[tot]=y;
w[tot]=z;
}
void build(int x,int y,int a,int b){
add(x,y,b-a);
add(y,x,0);
d[x]-=a;
d[y]+=a;
}
bool bfs(){
int u;
for(int i=minu;i<=maxu;i++){
lev[i]=-1;
cur[i]=first[i];
}
while(!q.empty()){
q.pop();
}
q.push(src);
lev[src]=0;
while(!q.empty()){
u=q.front();
q.pop();
for(int e=first[u];e;e=nnext[e]){
if(w[e]>0&&lev[to[e]]==-1){
q.push(to[e]);
lev[to[e]]=lev[u]+1;
if(to[e]==des){
return 1;
}
}
}
}
return 0;
}
int dinic(int u,int flow){
int res=0,delta;
if(u==des){
return flow;
}
for(int &e=cur[u];e;e=nnext[e]){
if(w[e]>0&&lev[to[e]]>lev[u]){
delta=dinic(to[e],min(w[e],flow-res));
if(delta){
res+=delta;
w[e]-=delta;
w[e^1]+=delta;
if(res==flow){
break;
}
}
}
}
if(res!=flow){
lev[u]=-1;
}
return res;
}
int main(){
int n,ss,tt,m,sum=0,a,b,dd;
minu=1;
scanf("%d%d",&n,&m);
ss=n+1;
tt=maxu=n+2;
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&a,&b,&c[i],&dd);
build(a,b,c[i],dd);
}
for(int i=1;i<=n;i++){
if(d[i]>0){
add(ss,i,d[i]);
add(i,ss,0);
sum+=d[i];
}
else{
add(i,tt,-d[i]);
add(tt,i,0);
}
}
src=ss;
des=tt;
while(bfs()){
sum-=dinic(src,1e9);
}
if(sum){
printf("NO");
return 0;
}
printf("YES\n");
for(int i=1;i<=m;i++){
printf("%d\n",w[2*i+1]+c[i]);
}
}
有源汇有上下界最大流
原汇到源连 INF 边，跑无源汇，再从原来的源到汇增广。
#include<bits/stdc++.h>
using namespace std;
int tot=1,src,des,minu,maxu,first[210],nnext[20510],to[20510],cur[210],lev[210],d[210],w[20510];
queue<int>q;
void add(int x,int y,int z){
nnext[++tot]=first[x];
first[x]=tot;
to[tot]=y;
w[tot]=z;
}
void build(int x,int y,int a,int b){
add(x,y,b-a);
add(y,x,0);
d[x]-=a;
d[y]+=a;
}
bool bfs(){
int u;
for(int i=minu;i<=maxu;i++){
lev[i]=-1;
cur[i]=first[i];
}
while(!q.empty()){
q.pop();
}
q.push(src);
lev[src]=0;
while(!q.empty()){
u=q.front();
q.pop();
for(int e=first[u];e;e=nnext[e]){
if(w[e]>0&&lev[to[e]]==-1){
q.push(to[e]);
lev[to[e]]=lev[u]+1;
if(to[e]==des){
return 1;
}
}
}
}
return 0;
}
int dinic(int u,int flow){
int res=0,delta;
if(u==des){
return flow;
}
for(int &e=cur[u];e;e=nnext[e]){
if(w[e]>0&&lev[to[e]]>lev[u]){
delta=dinic(to[e],min(w[e],flow-res));
if(delta){
res+=delta;
w[e]-=delta;
w[e^1]+=delta;
if(res==flow){
break;
}
}
}
}
if(res!=flow){
lev[u]=-1;
}
return res;
}
int main(){
int n,s,t,ss,tt,m,sum=0,a,b,c,dd;
minu=1;
scanf("%d%d%d%d",&n,&m,&s,&t);
ss=n+1;
tt=maxu=n+2;
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&a,&b,&c,&dd);
build(a,b,c,dd);
}
for(int i=1;i<=n;i++){
if(d[i]>0){
add(ss,i,d[i]);
add(i,ss,0);
sum+=d[i];
}
else{
add(i,tt,-d[i]);
add(tt,i,0);
}
}
add(t,s,1e9);
add(s,t,0);
src=ss;
des=tt;
while(bfs()){
sum-=dinic(src,1e9);
}
if(sum){
printf("please go home to sleep");
return 0;
}
src=s;
des=t;
while(bfs()){
sum+=dinic(src,1e9);
}
printf("%d",sum);
}
练习：P5192 Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流
有源汇有上下界最小流
同有源汇有上下界最大流，第一次满流后断掉汇到源的边从汇到源退流。
#include<bits/stdc++.h>
using namespace std;
int tot=1,src,des,minu,maxu,first[50010],nnext[500510],to[500510],cur[50010],lev[50010];
long long d[50010],w[500510];
queue<int>q;
void add(int x,int y,long long z){
nnext[++tot]=first[x];
first[x]=tot;
to[tot]=y;
w[tot]=z;
}
void build(int x,int y,long long a,long long b){
add(x,y,b-a);
add(y,x,0);
d[x]-=a;
d[y]+=a;
}
bool bfs(){
int u;
for(int i=minu;i<=maxu;i++){
lev[i]=-1;
cur[i]=first[i];
}
while(!q.empty()){
q.pop();
}
q.push(src);
lev[src]=0;
while(!q.empty()){
u=q.front();
q.pop();
for(int e=first[u];e;e=nnext[e]){
if(w[e]>0&&lev[to[e]]==-1){
q.push(to[e]);
lev[to[e]]=lev[u]+1;
if(to[e]==des){
return 1;
}
}
}
}
return 0;
}
long long dinic(int u,long long flow){
long long res=0,delta;
if(u==des){
return flow;
}
for(int &e=cur[u];e;e=nnext[e]){
if(w[e]>0&&lev[to[e]]>lev[u]){
delta=dinic(to[e],min(w[e],flow-res));
if(delta){
res+=delta;
w[e]-=delta;
w[e^1]+=delta;
if(res==flow){
break;
}
}
}
}
if(res!=flow){
lev[u]=-1;
}
return res;
}
int main(){
int n,s,t,ss,tt,m,a,b;
long long c,dd,sum=0;
minu=1;
scanf("%d%d%d%d",&n,&m,&s,&t);
ss=n+1;
tt=maxu=n+2;
for(int i=1;i<=m;i++){
scanf("%d%d%lld%lld",&a,&b,&c,&dd);
build(a,b,c,dd);
}
for(int i=1;i<=n;i++){
if(d[i]>0){
add(ss,i,d[i]);
add(i,ss,0);
sum+=d[i];
}
else{
add(i,tt,-d[i]);
add(tt,i,0);
}
}
add(t,s,1e9);
add(s,t,0);
src=ss;
des=tt;
while(bfs()){
sum-=dinic(src,1e9);
}
if(sum){
printf("please go home to sleep");
return 0;
}
src=t;
des=s;
sum=w[tot];
w[tot]=w[tot^1]=0;
while(bfs()){
sum-=dinic(src,1e9);
}
printf("%lld",sum);
}
有源汇有上下界可行费用流
有源汇有上下界可行流+SPFA
#include<bits/stdc++.h>
using namespace std;
int tot=1,sum,minu,maxu,src,des,first[310],nnext[200010],to[200010],w[200010],cost[200010],cur[310],d[310],dis[310],vis[310];
queue<int>q;
void add(int x,int y,int z,int c){
nnext[++tot]=first[x];
first[x]=tot;
to[tot]=y;
w[tot]=z;
cost[tot]=c;
}
void build(int x,int y,int a,int b,int c){
add(x,y,b-a,c);
add(y,x,0,-c);
d[x]-=a;
d[y]+=a;
}
bool bfs(){
int u;
while(!q.empty()){
q.pop();
}
for(int i=minu;i<=maxu;i++){
dis[i]=1e9;
vis[i]=0;
}
dis[src]=0;
q.push(src);
while(!q.empty()){
u=q.front();
q.pop();
vis[u]=0;
for(int e=first[u];e;e=nnext[e]){
if(w[e]>0&&dis[u]+cost[e]<dis[to[e]]){
dis[to[e]]=dis[u]+cost[e];
if(vis[to[e]]==0){
q.push(to[e]);
vis[to[e]]=1;
}
}
}
}
if(dis[des]==1e9){
return 0;
}
for(int i=minu;i<=maxu;i++){
if(dis[i]!=1e9){
vis[i]=0;
cur[i]=first[i];
}
}
return 1;
}
int dinic(int u,int flow){
int res=0,delta;
if(u==des){
sum+=dis[des]*flow;
return flow;
}
vis[u]=1;
for(int &e=cur[u];e;e=nnext[e]){
if(w[e]>0&&vis[to[e]]==0&&dis[u]+cost[e]==dis[to[e]]){
delta=dinic(to[e],min(flow-res,w[e]));
if(delta){
res+=delta;
w[e]-=delta;
w[e^1]+=delta;
if(res==flow){
break;
}
}
}
}
if(res==flow){
vis[u]=0;
}
return res;
}
int main(){
int n,m,a,b;
scanf("%d",&n);
des=maxu=n+2;
for(int i=1;i<=n;i++){
scanf("%d",&m);
while(m--){
scanf("%d%d",&a,&b);
build(i,a,1,1e5,b);
sum+=b;
}
if(i>=2){
build(i,n+1,0,1e5,0);
}
}
for(int i=1;i<=n;i++){
if(d[i]>0){
add(src,i,d[i],0);
add(i,src,0,0);
}
else{
add(i,des,-d[i],0);
add(des,i,0,0);
}
}
add(n+1,1,1e5,0);
add(1,n+1,0,0);
while(bfs()){
dinic(src,1e9);
}
printf("%d",sum);
}
练习：P4311 士兵占领
建模
匹配问题
建出二分图跑网络流即可。
练习：
带限制匹配
拆点，出点与入点之间连流量为限制的边。
练习：
带限制覆盖
无限制的连成一条链，源流出限制这么多流量。
或者离散化后每个点向下一个点连边，区间再连一连。
练习：
分配成两个集合并产生不同贡献
先全部都选，两边建新点向贡献涉及的点建边，然后减去最小割。
练习：
棋盘上的各种问题
考虑染色，然后转化为上述几种问题。
练习：
有限制函数值分配
一般是某几个点函数值与其他某些地方的值的差大于或小于某个值。
考虑最小割。每个点拆成函数值域个，在限制涉及的两列点中间连流量为 INF 的正向或反向边。
练习：
任务利益与机器花费问题
最大权闭合子图。源向正点权的点连流量为点权的边，负点权的点向汇连流量为点权相反数的边。原图中的点权看情况。一般设为 INF。
练习：