# 柒葉灬 的博客

### 网络流（最大流&费用流）

posted on 2019-07-24 19:19:36 | under 算法学习 |

# 最大流和费用流的应用

## 模板：

### 1.最大流

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1.5e4+100,maxm=5e6+100;
int n,m,k;
void clear(){
tot=1;
}
void add_edge(int u,int v,int c){
to[++tot]=v;
w[tot]=c;
}
void add_edges(int u,int v,int c){
}
int dep[maxn];
queue<int>Q;
int s,t;
bool bfs(){
while(!Q.empty())Q.pop();
memset(dep,0,sizeof(dep));
dep[s]=1;Q.push(s);
while(!Q.empty()){
int x=Q.front();
Q.pop();
int y=to[i];
if(!dep[y]&&w[i]){
dep[y]=dep[x]+1;
Q.push(y);
}
}
}
return dep[t];
}
int dfs(int x,int flow){
if(x==t)return flow;
int used=0;
for(int &i=cur[x];i;i=nxt[i]){
int y=to[i];
if(w[i]&&dep[y]==dep[x]+1){
int tmp=dfs(y,min(flow,w[i]));
w[i]-=tmp;w[i^1]+=tmp;
used+=tmp;
flow-=tmp;
if(flow==0)break;
}
}
if(flow)dep[x]=0;
return used;
}
long long dinic(){
long long flow=0;
while(bfs()){
for(int i=1;i<=n;i++)
flow+=dfs(s,2e9);
}
return flow;
}

int main(){
cin>>n>>m>>s>>t;
for(int i=1,x,y,z;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
}
cout<<dinic()<<endl;
return 0;
}


### 2.最小费用最大流

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl

using namespace std;
const int maxn=1005,maxm=2e5;
int s,t;
void clear(){
tot=1;
}
void add_edge(int u,int v,int flow,int cost){
to[++tot]=v;
w[tot]=cost;
f[tot]=flow;
}
void add_edges(int u,int v,int flow,int cost){
}
int dis[maxn],pos[maxn],last[maxn];
bool vis[maxn];
bool spfa(){
queue<int>Q;
while(!Q.empty())Q.pop();
memset(last,0,sizeof(last));
memset(dis,63,sizeof(dis));
Q.push(s);dis[s]=0;
while(!Q.empty()){
int x=Q.front();
Q.pop();
vis[x]=0;
int y=to[i];
if(f[i]&&dis[y]>dis[x]+w[i]){
dis[y]=dis[x]+w[i];
last[y]=x;
pos[y]=i;
if(!vis[y]){
vis[y]=1;
Q.push(y);
}
}
}
}
return last[t]>0;
}
void MCMF(){
int cost=0,flow=0;
while(spfa()){
int tmp=2e9;
for(int x=t;x!=s;x=last[x])
tmp=min(tmp,f[pos[x]]);

for(int x=t;x!=s;x=last[x]){
f[pos[x]]-=tmp;
f[pos[x]^1]+=tmp;
}
flow+=tmp;
cost+=tmp*dis[t];
}
}
int main(){
//连边
MCMF();
return 0;
}

## 题解：

### 1.方格取数（最大流，最小割）

#### 代码：

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int rx[]={0,0,1,-1};
const int ry[]={1,-1,0,0};
const int maxn=1e4+100,maxm=1e5;
int n,m,sum,mp[maxn][maxn];
int s,t;
void add_edge(int u,int v,int c){
to[++tot]=v;
w[tot]=c;
}
void add_edges(int u,int v,int c){
}
int dep[maxn];
bool bfs(){
queue<int>Q;
while(!Q.empty())Q.pop();
for(int i=1;i<=t;i++)
dep[i]=0;
Q.push(s);
dep[s]=1;
while(!Q.empty()){
int x=Q.front();
Q.pop();
int y=to[i];
if(dep[y]==0&&w[i]){
dep[y]=dep[x]+1;
Q.push(y);
}
}
}
return dep[t]!=0;
}
int dfs(int x,int flow){
if(x==t)return flow;
for(int &i=cur[x];~i;i=nxt[i]){
int y=to[i];
if(dep[y]==dep[x]+1&&w[i]){
int d=dfs(y,min(flow,w[i]));
if(d){
w[i]-=d;
w[i^1]+=d;
return d;
}
}
}
return 0;
}
void dinic(){
int ans=0;
while(bfs()){
for(int i=1;i<=t;i++)
while(int d=dfs(s,2e9))
ans+=d;
}
cout<<sum-ans<<endl;
}
int ID(int x,int y){
if(x<1||y<1||x>n||y>m)return -1;
return (x-1)*m+y;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&mp[i][j]),sum+=mp[i][j];
s=n*m+1,t=s+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
else {
for(int k=0;k<4;k++){
int y=ID(i+rx[k],j+ry[k]);
if(y==-1)continue;
}
}
dinic();
return 0;
}

### 2.餐巾计划（好题，最小费用最大流）

#### 思路2：

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=2e3+100,maxm=1e5+100;

int n,P,M,F,N,S;
int s,t;
int A[maxn];
void add_edge(int u,int v,int d,int flow){
to[++tot]=v;
w[tot]=d;
f[tot]=flow;
}
void add_edges(int u,int v,int d,int flow){
}
int dis[maxn],fa[maxn],last[maxn];
bool vis[maxn];
queue<int>Q;
bool spfa(){
memset(dis,127,sizeof(dis));
memset(last,0,sizeof(last));
while(!Q.empty())Q.pop();
Q.push(s);dis[s]=0;
while(!Q.empty()){
int x=Q.front();
Q.pop();
vis[x]=0;
int y=to[i];
if(f[i]&&dis[y]>dis[x]+w[i]){
dis[y]=dis[x]+w[i];
fa[y]=x;
last[y]=i;
if(!vis[y]){
vis[y]=1;
Q.push(y);
}
}
}
}
return last[t];
}
void solve(){
s=2*n+1;t=2*n+2;
int cost=0,flow=0;
for(int i=1;i<=n;i++){

cost+=A[i]*P;
}

while(spfa()){
int tmp=2e9;
for(int i=t;i!=s;i=fa[i]){
tmp=min(tmp,f[last[i]]);
}
for(int i=t;i!=s;i=fa[i]){
f[last[i]]-=tmp;
f[last[i]^1]+=tmp;
}
cost+=tmp*dis[t];
flow+=tmp;
}
cout<<cost<<endl;
}

int main(){
cin>>n>>P>>M>>F>>N>>S;
for(int i=1;i<=n;i++)
scanf("%d",&A[i]);
solve();
return 0;
}

### 3.星际转移（最大流）

#### 代码：

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1.5e4+100,maxm=5e6+100;
int n,m,k;
int h[25],r[25],num[25][25];

void add_edge(int u,int v,int c){
to[++tot]=v;
w[tot]=c;
}
void add_edges(int u,int v,int c){
}
int dep[maxn];
queue<int>Q;
int s,t;
bool bfs(){
while(!Q.empty())Q.pop();
memset(dep,0,sizeof(dep));
dep[s]=1;Q.push(s);
while(!Q.empty()){
int x=Q.front();
Q.pop();
int y=to[i];
if(!dep[y]&&w[i]){
dep[y]=dep[x]+1;
Q.push(y);
}
}
}
return dep[t];
}
int dfs(int x,int flow){
if(x==t)return flow;
for(int &i=cur[x];i;i=nxt[i]){
int y=to[i];
if(w[i]&&dep[y]==dep[x]+1){
int tmp=dfs(y,min(flow,w[i]));
if(tmp){
w[i]-=tmp;
w[i^1]+=tmp;
return tmp;
}
}
}
return 0;
}
int dinic(){
int flow=0;
while(bfs()){
for(int i=1;i<=t;i++)
while(int d=dfs(s,2e9))
flow+=d;
}
return flow;
}

int solve(){
s=800*(n+2)+1,t=s+1;
//n+1是月球 n+2是地球
int flow=0;
for(int i=0;i<799;i++){
for(int j=1;j<=m;j++){
int u=num[j][i%r[j]];
int v=num[j][(i+1)%r[j]];
}
for(int j=1;j<=n+2;j++)
flow+=dinic();
if(flow>=k)return i+1;
}
return 0;
}
int main(){
//  double sz=&cur2-&cur1;
//  cout<<sz/1024/1024<<endl;
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
scanf("%d%d",&h[i],&r[i]);
for(int j=0;j<r[i];j++){
scanf("%d",&num[i][j]);
if(num[i][j]<=0)num[i][j]+=n+2;
}
}
cout<<solve()<<endl;
return 0;
}

### 4.最长 k 可重区间集（好题，费用流）

#### 思路：

$l[i]$ 与 $r[i]$ 连边，

#### 代码：

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl

using namespace std;
const int maxn=1005,maxm=2e5;
int s,t,n,K;
int l[maxn],r[maxn],val[maxn];
int q,C[maxn];

void add_edge(int u,int v,int flow,int cost){
to[++tot]=v;
w[tot]=cost;
f[tot]=flow;
}
void add_edges(int u,int v,int flow,int cost){
}
int dis[maxn],pos[maxn],last[maxn];
bool vis[maxn];
bool spfa(){
queue<int>Q;
while(!Q.empty())Q.pop();
memset(last,0,sizeof(last));
memset(dis,63,sizeof(dis));
Q.push(s);dis[s]=0;
while(!Q.empty()){
int x=Q.front();
Q.pop();
vis[x]=0;
int y=to[i];
if(f[i]&&dis[y]>dis[x]+w[i]){
dis[y]=dis[x]+w[i];
last[y]=x;
pos[y]=i;
if(!vis[y]){
vis[y]=1;
Q.push(y);
}
}
}
}
return last[t]>0;
}
void MCMF(){
int cost=0,flow=0;
while(spfa()){
int tmp=2e9;
for(int x=t;x!=s;x=last[x])
tmp=min(tmp,f[pos[x]]);

for(int x=t;x!=s;x=last[x]){
f[pos[x]]-=tmp;
f[pos[x]^1]+=tmp;
}
flow+=tmp;
cost+=tmp*dis[t];
}
cout<<-cost<<endl;
}
int main(){
cin>>n>>K;
for(int i=1;i<=n;i++){
scanf("%d%d",&l[i],&r[i]);
if(l[i]>r[i])swap(l[i],r[i]);
C[++q]=l[i];C[++q]=r[i];
val[i]=r[i]-l[i];
}
sort(C+1,C+1+q);
q=unique(C+1,C+1+q)-C-1;
for(int i=1;i<=n;i++){
l[i]=lower_bound(C+1,C+1+q,l[i])-C;
r[i]=lower_bound(C+1,C+1+q,r[i])-C;
}
s=q+1;t=s+1;
for(int i=1;i<q;i++)
for(int i=1;i<=n;i++){
}
MCMF();
return 0;
}


### 5.太空飞行计划（好题，最大权闭合图）

#### 思路：

（十分符合最大权闭合图模型）

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=205,maxm=1e5;
int n,m;
int A[maxn],B[maxn];
int s,t;
void clear(){
tot=-1;
}
void add_edge(int u,int v,int c){
to[++tot]=v;
w[tot]=c;
}
void add_edges(int u,int v,int c){
}
int dep[maxn];
bool bfs(){
queue<int>Q;
while(!Q.empty())Q.pop();
for(int i=1;i<=t;i++)
dep[i]=0;
dep[s]=1;
Q.push(s);
while(!Q.empty()){
int x=Q.front();
Q.pop();
int y=to[i];
if(dep[y]==0&&w[i]){
dep[y]=dep[x]+1;
Q.push(y);
}
}
}
return dep[t]!=0;
}
int dfs(int x,int flow){
if(x==t)return flow;
for(int &i=cur[x];~i;i=nxt[i]){
int y=to[i];
if(w[i]&&dep[y]==dep[x]+1){
int tmp=dfs(y,min(flow,w[i]));
if(tmp){
w[i]-=tmp;
w[i^1]+=tmp;
return tmp;
}
}
}
return 0;
}
void dinic(){
int res=0;
while(bfs()){
for(int i=1;i<=t;i++)
while(int d=dfs(s,2e9))
res+=d;
}

}
bool mark[maxn];
void solve(){
dinic();
for(int i=1;i<=n+m;i++)
if(dep[i]){
mark[i]=1;
}
int ans=0;
for(int i=1,p=0;i<=m;i++){
if(mark[i]){
if(p)putchar(' ');
else p=1;
printf("%d",i);
ans+=A[i];
}
}
puts("");
for(int i=1,p=0;i<=n;i++){
if(mark[i+m]){
ans-=B[i];
if(p)putchar(' ');
else p=1;
printf("%d",i);
}
}
puts("");
printf("%d\n",ans);
}
int main(){
clear();
cin>>m>>n;
s=n+m+1,t=n+m+2;
for(int i=1;i<=m;i++){
scanf("%d",&A[i]);
char c=' ';
while(c==' '){
int res=0;
while((c=getchar())<48);
do res=(res<<1)+(res<<3)+(c^48);
while((c=getchar())>47);
}
}
for(int i=1;i<=n;i++){
scanf("%d",&B[i]);
}
solve();
return 0;
}

### 6.Harmonious Army（神题，最小割）

#### 思路：

$$a+b=B+C$$ $$c+d=A+B$$ $$a+e+d=b+e+c=A+C$$

$$a=b=\frac{B+C}{2}$$ $$c=d=\frac{A+B}{2}$$ $$e=-B+\frac{A+C}{2}$$

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=505*2,maxm=1e5;
int n,m,s,t;
long long w[maxm];
long long ans,sum[2][maxn];
void clear(){
memset(sum,0,sizeof(sum));
tot=1;ans=0;
}
void add_edge(int u,int v,long long c){
to[++tot]=v;
w[tot]=c;
}
void add_edges(int u,int v,long long c){
}
int dep[maxn];
bool bfs(){
queue<int>Q;
while(!Q.empty())Q.pop();
for(int i=1;i<=t;i++)
dep[i]=0;
dep[s]=1;
Q.push(s);
while(!Q.empty()){
int x=Q.front();
Q.pop();
int y=to[i];
if(dep[y]==0&&w[i]){
dep[y]=dep[x]+1;
Q.push(y);
}
}
}
return dep[t]!=0;
}
long long dfs(int x,long long flow){
if(x==t)return flow;
for(int &i=cur[x];i;i=nxt[i]){
int y=to[i];
if(w[i]&&dep[y]==dep[x]+1){
int tmp=dfs(y,min(flow,w[i]));
if(tmp){
w[i]-=tmp;
w[i^1]+=tmp;
return tmp;
}
}
}
return 0;
}
long long dinic(){
long long res=0;
while(bfs()){
for(int i=1;i<=t;i++)
while(long long d=dfs(s,2e18))
res+=d;
}
return res;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
clear();
s=2*n+1;t=s+1;
for(int i=1,u,v,a,b,c;i<=m;i++){
scanf("%d%d%d%d%d",&u,&v,&a,&b,&c);
a<<=1;b<<=1;c<<=1;
ans+=a+b+c;
}