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

# 最大流和费用流的应用 ------ ## 模板： ### 1.最大流 ```cpp #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 tot=1,cur[maxn],head[maxn],to[maxm],nxt[maxm],w[maxm]; void clear(){ tot=1; memset(head,0,sizeof(head)); } void add_edge(int u,int v,int c){ to[++tot]=v; nxt[tot]=head[u]; w[tot]=c; head[u]=tot; } void add_edges(int u,int v,int c){ add_edge(u,v,c); add_edge(v,u,0); } 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(); for(int i=head[x];i;i=nxt[i]){ 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++) cur[i]=head[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); add_edges(x,y,z); } cout<<dinic()<<endl; return 0; } ``` ------ ### 2.最小费用最大流 ```cpp #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; int tot=1,head[maxn],to[maxm],nxt[maxm],w[maxm],f[maxm]; void clear(){ memset(head,0,sizeof(head)); tot=1; } void add_edge(int u,int v,int flow,int cost){ to[++tot]=v; nxt[tot]=head[u]; head[u]=tot; w[tot]=cost; f[tot]=flow; } void add_edges(int u,int v,int flow,int cost){ add_edge(u,v,flow,cost); add_edge(v,u,0,-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; for(int i=head[x];i;i=nxt[i]){ 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.方格取数（最大流，最小割） #### 题意： 给n行m列的矩阵，取出不相邻的若干个数，使得权值和最大。 #### 思路： 最大流流出去的总是权值最小的，这题如果直接写不好写， 考虑换一种方向： 选出去不要哪些点，总和减去这个值就是答案。 #### 代码： ```cpp #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; int tot=-1,head[maxn],cur[maxn],to[maxm],nxt[maxm],w[maxm]; void add_edge(int u,int v,int c){ to[++tot]=v; nxt[tot]=head[u]; w[tot]=c; head[u]=tot; } void add_edges(int u,int v,int c){ add_edge(u,v,c); add_edge(v,u,0); } 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(); for(int i=head[x];~i;i=nxt[i]){ 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++) cur[i]=head[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]; memset(head,-1,sizeof(head)); s=n*m+1,t=s+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(i+j&1)add_edges(ID(i,j),t,mp[i][j]); else { add_edges(s,ID(i,j),mp[i][j]); for(int k=0;k<4;k++){ int y=ID(i+rx[k],j+ry[k]); if(y==-1)continue; add_edges(ID(i,j),y,2e9); } } dinic(); return 0; } ``` **这题用了一个思想：利用网络流求出最小需要舍弃的权值** **答案则变为总和减去最小代价** **而这种思想就是“最小割”** 定义：去除一些边，使得汇点**到不了**源点。 而最后保留的就是选出最优的答案。 ### 2.餐巾计划（好题，最小费用最大流） #### 思路1： 处理流量很麻烦，不妨直接设流量就是每天需要之和， 即先买了所有的餐巾， 洗餐巾就相当于退掉，向汇点连边。 #### 思路2： 根据贪心的思路，每天的餐巾买了要么直接洗，要么就一直不洗，  下面是思路1的代码： ```cpp #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]; int tot=1,head[maxn],to[maxm],nxt[maxm],f[maxm],w[maxm]; void add_edge(int u,int v,int d,int flow){ to[++tot]=v; nxt[tot]=head[u]; w[tot]=d; f[tot]=flow; head[u]=tot; } void add_edges(int u,int v,int d,int flow){ add_edge(u,v,d,flow); add_edge(v,u,-d,0); } 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; for(int i=head[x];i;i=nxt[i]){ 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++){ add_edges(s,i,0,A[i]); add_edges(i+n,t,0,A[i]); if(i+M<=n)add_edges(i,i+M+n,F-P,2e9); if(i+N<=n)add_edges(i,i+N+n,S-P,2e9); if(i<n)add_edges(i,i+1,0,2e9); else add_edges(i,t,0,2e9); 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.星际转移（最大流） #### 思路： 对于每一个时间的每一个点建一个点， 如果跑最大流之后流量达不到人数， 说明还需要时间， 那么就继续建新点，连新边， 直到找到最小的时间或者输出-1. #### 代码： ```cpp #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]; int tot=1,cur[maxn],head[maxn],to[maxm],nxt[maxm],w[maxm]; void add_edge(int u,int v,int c){ to[++tot]=v; nxt[tot]=head[u]; w[tot]=c; head[u]=tot; } void add_edges(int u,int v,int c){ add_edge(u,v,c); add_edge(v,u,0); } 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(); for(int i=head[x];i;i=nxt[i]){ 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++) cur[i]=head[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++){ add_edges(s,i*(n+2)+n+2,2e9); add_edges((i+1)*(n+2)+n+1,t,2e9); for(int j=1;j<=m;j++){ int u=num[j][i%r[j]]; int v=num[j][(i+1)%r[j]]; add_edges(i*(n+2)+u,(i+1)*(n+2)+v,h[j]); } for(int j=1;j<=n+2;j++) add_edges(i*(n+2)+j,(i+1)*(n+2)+j,2e9); 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]$连边， 汇点与$1$连流量为$K$的边 最后跑出来的最小费用的相反数就是最大的答案。 #### 代码： ```cpp #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]; int tot=1,head[maxn],to[maxm],nxt[maxm],w[maxm],f[maxm]; void add_edge(int u,int v,int flow,int cost){ to[++tot]=v; nxt[tot]=head[u]; head[u]=tot; w[tot]=cost; f[tot]=flow; } void add_edges(int u,int v,int flow,int cost){ add_edge(u,v,flow,cost); add_edge(v,u,0,-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; for(int i=head[x];i;i=nxt[i]){ 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++) add_edges(i,i+1,2e9,0); add_edges(s,1,K,0); add_edges(q,t,K,0); for(int i=1;i<=n;i++){ add_edges(l[i],r[i],1,-val[i]); } MCMF(); return 0; } ``` ### 5.太空飞行计划（好题，最大权闭合图） 先介绍一下最大权闭合图什么意思： 给一个有向图，每个点有一个权值， 若选择一个点，那么他的后继节点也都要选， 求最大权值是多少。 #### 思路： 这题若选择了一个任务， 那么所连接的所有器材也都要选上， 任务的权值为正，器材的权值为负， 求得就是最大的利润。 （十分符合最大权闭合图模型） 处理最大权闭合子图： 将源点$s$与所有正权点连边， 将所有负权点与汇点$t$连边， 原图中的所有边变为流量为$INF$的边， 流出的最大流即最小割，即最大权闭合图。 **还有个问题就是决策** 若源点连向正权值的边流量不为$0$， 则说明这条边没有被割掉， 所以说明这个点要选上， 负权点根据正权点选择搞就行了。 ```cpp #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; int tot,cur[maxn],head[maxn],to[maxm],nxt[maxm],w[maxm]; void clear(){ memset(head,-1,sizeof(head)); tot=-1; } void add_edge(int u,int v,int c){ to[++tot]=v; nxt[tot]=head[u]; w[tot]=c; head[u]=tot; } void add_edges(int u,int v,int c){ add_edge(u,v,c); add_edge(v,u,0); } 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(); for(int i=head[x];~i;i=nxt[i]){ 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++) cur[i]=head[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]); add_edges(s,i,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); add_edges(i,res+m,2e9); } } for(int i=1;i<=n;i++){ scanf("%d",&B[i]); add_edges(i+m,t,B[i]); } solve(); return 0; } ``` ### 6.Harmonious Army（神题，最小割） #### 题意： 给$n$个点染黑色或白色，$m$个关系，若$u_i$与$v_i$都为黑则贡献为$a_i$，若都是白色则为$c_i$，否则是$b_i$。（$b_i=\frac{a_i}{3}+\frac{c_i}{4}$） #### 思路： 考虑到正着选不好写，无法转换成最大贡献 应该想到转换为最小割问题，写最小贡献割。 建图确实很神奇，就算想到了最小割也不一定会写， 图建出来为下图所示：  对于一对关系有四种割法，正好可以对应$4$种选择， $$ 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} $$ ```cpp #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; int tot,cur[maxn],head[maxn],to[maxm],nxt[maxm]; long long w[maxm]; long long ans,sum[2][maxn]; void clear(){ memset(sum,0,sizeof(sum)); memset(head,0,sizeof(head)); tot=1;ans=0; } void add_edge(int u,int v,long long c){ to[++tot]=v; nxt[tot]=head[u]; w[tot]=c; head[u]=tot; } void add_edges(int u,int v,long long c){ add_edge(u,v,c); add_edge(v,u,0); } 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(); for(int i=head[x];i;i=nxt[i]){ 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++) cur[i]=head[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; add_edges(u,v,-b+(a+c)/2); add_edges(v,u,-b+(a+c)/2); sum[0][u]+=(b+c)>>1; sum[0][v]+=(b+c)>>1; sum[1][u]+=(a+b)>>1; sum[1][v]+=(a+b)>>1; } for(int i=1;i<=n;i++){ add_edges(s,i,sum[0][i]); add_edges(i,t,sum[1][i]); } printf("%lld\n",(ans-dinic())/2); } return 0; } ```