网络流真的是一个什么强大的算法啦。令人头疼的是网络流的灵活应用之广泛，网络流的题目建图方式也是千奇百怪，所以蒟蒻打算总结一下网络流的建图方式。秉着不重复造轮子的原则（其实是博主又菜又想找个借口），网上大佬写的好的就直接贴网址了。 （更新ing）
大佬强无敌的总结：https://www.cnblogs.com/victorique/p/8560656.html#autoid-1-10-3
最小割应用：https://wenku.baidu.com/view/87ecda38376baf1ffc4fad25.html
最大权闭合子图：https://blog.csdn.net/can919/article/details/77603353
题目集合：https://blog.csdn.net/corsica6/article/details/88045843
经典模型：
这些是上面博客大佬总结的经典模型，我也试着总结一下。
题目练习：
POJ-2987
最大权闭合子图入门题。按照上面说的连边建图跑最小割。求它的最小割，割掉后，与源点s连通的点构成最大权闭合子图，权值为（正权值之和-最小割）。所以在残余网络上从源点s开始沿着非满流边(即没割掉的边)dfs即可，遇到的就是选择的点。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; typedef long long LL; const int N=1e4+10; const int M=2e5+100; const LL INF=1LL<<60; int n,m,s,t; LL sum; int tot=1,head[N],nxt[N<<6],ver[N<<6]; LL edge[N<<6]; queue<int> q; void add_edge(int x,int y,LL z) { ver[++tot]=y; edge[tot]=z; nxt[tot]=head[x]; head[x]=tot; ver[++tot]=x; edge[tot]=0; nxt[tot]=head[y]; head[y]=tot; } int d[N]; bool bfs() { memset(d,0,sizeof(d)); while (!q.empty()) q.pop(); q.push(s); d[s]=1; while (!q.empty()) { int x=q.front(); q.pop(); for (int i=head[x];i;i=nxt[i]) { if (edge[i] && !d[ver[i]]) { q.push(ver[i]); d[ver[i]]=d[x]+1; if (ver[i]==t) return 1; } } } return 0; } LL dinic(int x,LL flow) { if (x==t) return flow; LL rest=flow,k; for (int i=head[x];i && rest;i=nxt[i]) if (edge[i] && d[ver[i]]==d[x]+1){ k=dinic(ver[i],min(rest,edge[i])); if (!k) d[ver[i]]=0; edge[i]-=k; edge[i^1]+=k; rest-=k; } return flow-rest; } bool vis[N]; int dfsp(int x) { int ret=1; vis[x]=1; for (int i=head[x];i;i=nxt[i]) { int y=ver[i]; if (edge[i]>0 && !vis[y]) ret+=dfsp(y); } return ret; } int main() { scanf("%d%d",&n,&m); s=0; t=n+1; for (int i=1;i<=n;i++) { LL x; scanf("%lld",&x); if (x>=0) add_edge(s,i,x),add_edge(i,s,0),sum+=x; if (x<0) add_edge(i,t,-x),add_edge(t,i,0); } for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add_edge(x,y,INF); add_edge(y,x,0); } LL flow; while (bfs()) while (flow=dinic(s,INF)) sum-=flow; cout<<dfsp(s)-1<<" "<<sum<<endl; return 0; }
洛谷P1345 奶牛的电信
比较明显的最小割。但是注意每台电脑只能用一次，所以要拆点限制每个点的流量为1。有一个细节：起点和终点的点不用限制流量为1(虽然题目似乎没提c1/c2不可破坏)。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int N=10000+10; const int M=100000+100; const int INF=0x3f3f3f3f; int n,m,s,t; struct edge{ int nxt,to,cap; }edges[M<<1]; int cnt=1,head[N],cur[N]; void add_edge(int x,int y,int z) { edges[++cnt].nxt=head[x]; edges[cnt].to=y; edges[cnt].cap=z; head[x]=cnt; } int dep[N]; queue<int> q; 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=edges[i].nxt) { edge e=edges[i]; if (!dep[e.to] && e.cap) { dep[e.to]=dep[x]+1; q.push(e.to); } } } return dep[t]; } int dfs(int x,int lim) { if (x==t || !lim) return lim; int ret=0; for (int& i=cur[x];i;i=edges[i].nxt) { edge e=edges[i]; if (dep[x]+1==dep[e.to] && e.cap) { int flow=dfs(e.to,min(lim,e.cap)); if (flow>0) { edges[i].cap-=flow; edges[i^1].cap=+flow; ret+=flow; lim-=flow; if (!lim) break; } } } return ret; } int Dinic() { int maxflow=0; while (bfs()) { for (int i=s;i<=t;i++) cur[i]=head[i]; //当前弧优化 while (int flow=dfs(s,INF)) maxflow+=flow; } return maxflow; } int main() { scanf("%d%d%d%d",&n,&m,&s,&t); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add_edge(x+n,y,1); add_edge(y,x+n,0); add_edge(y+n,x,1); add_edge(x,y+n,0); } for (int i=1;i<=n;i++) add_edge(i,i+n,1),add_edge(i+n,i,0); add_edge(s,s+n,INF); add_edge(s+n,s,0); add_edge(t,t+n,INF); add_edge(t+n,t,0); add_edge(0,s,INF); add_edge(s,0,0); add_edge(t+n,2*n+1,INF); add_edge(2*n+1,t+n,0); s=0; t=2*n+1; cout<<Dinic()<<endl; return 0; }
洛谷P3159 交互棋子
洛谷P2825 游戏
这道题有意思也很有代表性。对于这种棋盘有互斥关系的题目都可以往网络流方面想一想。这题也是行列互斥但是注意到因为硬石头的存在导致行/列能够放多个炸弹，所以此题建图应该根据硬石头把每行/每列分成不仅仅是一行一列而是把极大没有硬石头的一串当成一行一列。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int N=10000+10; const int M=100000+100; const int INF=0x3f3f3f3f; int n,m,s,t; struct edge{ int nxt,to,cap; }edges[M<<1]; int cnt=1,head[N],cur[N]; char mp[55][55]; int r[55][55],c[55][55]; void add_edge(int x,int y,int z) { edges[++cnt].nxt=head[x]; edges[cnt].to=y; edges[cnt].cap=z; head[x]=cnt; } int dep[N]; queue<int> q; 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=edges[i].nxt) { edge e=edges[i]; if (!dep[e.to] && e.cap) { dep[e.to]=dep[x]+1; q.push(e.to); } } } return dep[t]; } int dfs(int x,int lim) { if (x==t || !lim) return lim; int ret=0; for (int& i=cur[x];i;i=edges[i].nxt) { edge e=edges[i]; if (dep[x]+1==dep[e.to] && e.cap) { int flow=dfs(e.to,min(lim,e.cap)); if (flow>0) { edges[i].cap-=flow; edges[i^1].cap=+flow; ret+=flow; lim-=flow; if (!lim) break; } } } return ret; } int Dinic() { int maxflow=0; while (bfs()) { for (int i=s;i<=t;i++) cur[i]=head[i]; //当前弧优化 while (int flow=dfs(s,INF)) maxflow+=flow; } return maxflow; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%s",mp[i]+1); int num=0; for (int i=1;i<=n;i++) { num++; for (int j=1;j<=m;j++) { if (mp[i][j-1]=='#') num++; r[i][j]=num; } } for (int j=1;j<=m;j++) { num++; for (int i=1;i<=n;i++) { if (mp[i-1][j]=='#') num++; c[i][j]=num; } } s=0; t=num+1; for (int i=1;i<=r[n][m];i++) add_edge(s,i,1),add_edge(i,s,0); for (int i=r[n][m]+1;i<=c[n][m];i++) add_edge(i,t,1),add_edge(t,i,0); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (mp[i][j]=='*') { add_edge(r[i][j],c[i][j],INF); add_edge(c[i][j],r[i][j],0); } cout<<Dinic()<<endl; return 0; }
BZOJ-4950
题意：给出一个俯视图，每个数字代表该格子的箱子高度。我们可以从这些格子中取走一些箱子但是要使得取走后的图正视图，左视图，俯视图都不能改变。问能取走的最大箱子数。
解法：这道题没想到(是真的菜qwq)。首先容易想到每行每列的最大值不能选，然后任何不是最大值的格子就取剩一个（保证俯视图）。我们发现这样的话会有浪费，若存在某行某列的最大值相等，其实我们可以把最大值放在他们的交点处，这样能够省一个最大值，但是注意并不是只要行列相等就能省，因为一个交点最多只能代表一行一列多了就不行。那么怎么做呢？我们仔细梳理这个问题：首先还是必须行列最大值相等才能考虑省，然后注意到多个最大值相等的行列，行只能用一次，列也只能用一次，然后两个还没用过的相等行列凑到一起就能省一个最大值。哦！！这不就是二分图匹配。没错！所以我们把行当左边点，列当右边点，做二分图匹配即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=200+10; 4 int n,m,mat[N]; 5 bool vis[N]; 6 vector<int> G[N]; 7 int mp[110][110],rmax[110],cmax[110]; 8 9 bool match(int x) { 10 for (int i=0;i<G[x].size();i++) { 11 int y=G[x][i]; 12 if (!vis[y]) { 13 vis[y]=true; 14 if (mat[y]==0 || match(mat[y])) { 15 mat[y]=x; 16 return true; 17 } 18 } 19 } 20 return false; 21 } 22 23 signed main() 24 { 25 scanf("%d%d",&n,&m); 26 long long ans=0; 27 for (int i=1;i<=n;i++) 28 for (int j=1;j<=m;j++) { 29 scanf("%d",&mp[i][j]); 30 rmax[i]=max(rmax[i],mp[i][j]); 31 cmax[j]=max(cmax[j],mp[i][j]); 32 if (mp[i][j]) ans+=mp[i][j]-1; 33 } 34 for (int i=1;i<=n;i++) if (rmax[i]) ans-=rmax[i]-1; 35 for (int j=1;j<=m;j++) if (cmax[j]) ans-=cmax[j]-1; 36 for (int i=1;i<=n;i++) 37 for (int j=1;j<=m;j++) 38 if (rmax[i]==cmax[j] && mp[i][j]) 39 G[i].push_back(j+n),G[j+n].push_back(i); 40 for (int i=1;i<=n;i++) { 41 memset(vis,0,sizeof(vis)); 42 if (match(i)) ans+=rmax[i]-1; 43 } 44 cout<<ans<<endl; 45 return 0; 46 }
洛谷P2053
题意：m个工作人员修n辆车，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。
解法：感觉这道题还蛮有意思的。我们发现对于某个人如果他的修车顺序是w1->w2->w3,那么等待时间就是w1*3+w2*2+w3*1。也就是说每个人倒数第一辆修的时间是1*原时间，第二辆是2*原时间，第n辆修是n*原时间。看到数据量很小，那么我们直接暴力拆点。左边拆n个车的点，右边每个人拆成n个点（i，j）表示第i个人倒数第j辆修的点。两边分别向源汇点连容量1费用0的边，中间就要连边费用就是相应付出的时间，那么第i辆车给第j个工作人员倒数第k修的代价就是 a[i][j]*k 。连边跑费用流此题可解。
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; const int N=5000+10; const int M=50000+10; const int INF=0x3f3f3f3f; int n,m,s,t,maxflow,mincost; struct edge{ int nxt,to,cap,cost; }edges[M<<1]; int cnt=1,head[N],pre[N],a[66][66]; void add_edge(int x,int y,int z,int c) { edges[++cnt].nxt=head[x]; edges[cnt].to=y; edges[cnt].cap=z; edges[cnt].cost=c; head[x]=cnt; } queue<int> q; int dis[N],lim[N]; bool inq[N]; bool spfa(int s,int t) { while (!q.empty()) q.pop(); memset(dis,0x3f,sizeof(dis)); memset(inq,0,sizeof(inq)); dis[s]=0; inq[s]=1; lim[s]=INF; q.push(s); while (!q.empty()) { int x=q.front(); q.pop(); for (int i=head[x];i;i=edges[i].nxt) { edge e=edges[i]; if (e.cap && dis[x]+e.cost<dis[e.to]) { dis[e.to]=dis[x]+e.cost; pre[e.to]=i; //即e.to这个点是从i这条边来的 lim[e.to]=min(lim[x],e.cap); if (!inq[e.to]) { q.push(e.to); inq[e.to]=1; } } } inq[x]=0; } return !(dis[t]==INF); } void MCMF() { maxflow=0; mincost=0; while (spfa(s,t)) { int now=t; maxflow+=lim[t]; mincost+=lim[t]*dis[t]; while (now!=s) { edges[pre[now]].cap-=lim[t]; edges[pre[now]^1].cap+=lim[t]; now=edges[pre[now]^1].to; } } } int id(int x,int y) { return n+(x-1)*n+y; } int main() { scanf("%d%d",&m,&n); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&a[i][j]); s=0; t=n+n*m+1; for (int i=1;i<=n;i++) add_edge(s,i,1,0),add_edge(i,s,0,0); for (int i=n+1;i<=n+n*m;i++) add_edge(i,t,1,0),add_edge(t,i,0,0); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int k=1;k<=n;k++) add_edge(i,id(j,k),1,k*a[i][j]),add_edge(id(j,k),i,0,-k*a[i][j]); MCMF(); printf("%.2lf ",(double)mincost/n); return 0; }