爱站程序员基地最大流
Dinic
建图时必须要建一条流量为0的反向边：建立反向边是为了增加重新调整的机会，即保障解是最优的。
应用场景：
1、裸的最大流
2、二分图的最大匹配：建一个点S，连到二分图的集合A中；建一个点T，连到二分图的集合B中。再将所有的集合A中的点与 集合B中的点相连。全部边权设为1，跑一遍最大流，结果即为二分图的最大匹配。
3、最小割：图中所有的割中，边权值和最小的割为最小割。 在单源单汇流量图中，最大流等于最小割。
4、求最大权闭合图（这里）：权值=正点权之和-最小割
[code]#include<bits/stdc++.h>#define ll long long#define MOD 998244353#define INF 0x3f3f3f3f#define mem(a,x) memset(a,x,sizeof(a))#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);using namespace std;const int maxn= 200 + 5; //点const int maxm= 2000 + 5; //边int n,m,cnt=0;int head[maxn];int dis[maxn];struct node{int e,v,nxt;}edge[maxm<<1];inline void addl(int u,int v,int w){edge[cnt].e=v;edge[cnt].v=w;edge[cnt].nxt=head[u];head[u]=cnt++;}bool bfs(){mem(dis,-1);dis[1]=0;queue<int>q;q.push(1);while(!q.empty()){int r=q.front();q.pop();for(int i=head[r];i!=-1;i=edge[i].nxt){int j=edge[i].e;if(dis[j]==-1&&edge[i].v){dis[j]=dis[r]+1;q.push(j);}}}return dis!=-1;}int dfs(int u,int flo){if(u==n)return flo;int detla=flo;for(int i=head[u];i!=-1;i=edge[i].nxt){int v=edge[i].e;if(dis[v]==(dis[u]+1)&&edge[i].v>0){int d=dfs(v,min(detla,edge[i].v));edge[i].v-=d;edge[i^1].v+=d;detla-=d;if(detla==0)break;}}return flo-detla;}int Dinic(){int ans=0;while(bfs()){ans+=dfs(1,INF);}return ans;}int main(){while(~scanf(\"%d %d\",&n,&m)){mem(head,-1);for(int i=1;i<=m;i++){int a,b,c;scanf(\"%d %d %d\",&a,&b,&c);addl(a,b,c);addl(b,a,0); //*}printf(\"%d\\n\",Dinic());}return 0;}
最小费用最大流
spfa
反边的流量是0，花费是相反数。
[code]#include<bits/stdc++.h>#define ll long long#define MOD 998244353#define INF 0x3f3f3f3f#define mem(a,x) memset(a,x,sizeof(a))#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);using namespace std;const int maxn = 100010;bool vis[maxn];int n,m,s,t;int dis[maxn],pre[maxn],last[maxn],flow[maxn],maxflow,mincost;struct node{int to,nxt,flow,dis; //flow流量 dis花费}edge[maxn];int head[maxn],cnt=0;void addl(int u,int v,int flow,int dis){edge[cnt].to=v;edge[cnt].flow=flow;edge[cnt].dis=dis;edge[cnt].nxt=head[u];head[u]=cnt++;}bool spfa(int s,int t){mem(dis,INF);mem(flow,INF);mem(vis,0);queue<int>q;q.push(s);vis[s]=1;dis[s]=0;pre[t]=-1;while(!q.empty()){int now=q.front();q.pop();vis[now]=0;for(int i=head[now];i!=-1;i=edge[i].nxt){if(edge[i].flow>0&&dis[edge[i].to]>dis[now]+edge[i].dis){dis[edge[i].to]=dis[now]+edge[i].dis;pre[edge[i].to]=now;last[edge[i].to]=i;flow[edge[i].to]=min(flow[now],edge[i].flow);if(!vis[edge[i].to]){vis[edge[i].to]=1;q.push(edge[i].to);}}}}return pre[t]!=-1;}void MCMF(){while(spfa(s,t)){int now=t;maxflow+=flow[t];mincost+=flow[t]*dis[t];while(now!=s){edge[last[now]].flow-=flow[t];edge[last[now]^1].flow+=flow[t];now=pre[now];}}}int main(){mem(head,-1);mem(pre,-1);cnt=0;maxflow=0;mincost=0;scanf(\"%d %d %d %d\",&n,&m,&s,&t);for(int i=1;i<=m;i++){int a,b,c,d;scanf(\"%d %d %d %d\",&a,&b,&c,&d);addl(a,b,c,d);addl(b,a,0,-d); //反边的流量是0，花费是相反数}MCMF();printf(\"%d %d\",maxflow,mincost);return 0;}
例题
1、Going Home POJ – 2195
题目大意：一幅图上有若干个人和房子，房子和人的数量相等，每个格子的距离是1，问你所有人回到任意一个房子且没有相同房子时，最少的花费是多少。
解题思路：建立一个源点与每个人相连，花费为0，流量为1，把每个人和每个房子都连接，边的权值（花费）就是距离，流量设为1，建立一个汇点，把每个房子与汇点连接，花费为0，流量为1，跑一遍最小花费最大流即可。
代码：
[code]#include <iostream>#include <cstdio>#include <fstream>#include <algorithm>#include <cmath>#include <deque>#include <vector>#include <queue>#include <string>#include <cstring>#include <map>#include <stack>#include <set>#define ll long long#define ull unsigned long long#define MOD 998244353#define INF 0x3f3f3f3f#define mem(a,x) memset(a,x,sizeof(a))#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);using namespace std;const int maxn = 100010;bool vis[maxn];int n,m,s,t;int dis[maxn],pre[maxn],last[maxn],flow[maxn],maxflow,mincost;struct node{int to,nxt,flow,dis; //flow流量 dis花费}edge[maxn];int head[maxn],cnt=0;void addl(int u,int v,int flow,int dis){edge[cnt].to=v;edge[cnt].flow=flow;edge[cnt].dis=dis;edge[cnt].nxt=head[u];head[u]=cnt++;}bool spfa(int s,int t){mem(dis,INF);mem(flow,INF);mem(vis,0);queue<int>q;q.push(s);vis[s]=1;dis[s]=0;pre[t]=-1;while(!q.empty()){int now=q.front();q.pop();vis[now]=0;for(int i=head[now];i!=-1;i=edge[i].nxt){if(edge[i].flow>0&&dis[edge[i].to]>dis[now]+edge[i].dis){dis[edge[i].to]=dis[now]+edge[i].dis;pre[edge[i].to]=now;last[edge[i].to]=i;flow[edge[i].to]=min(flow[now],edge[i].flow);if(!vis[edge[i].to]){vis[edge[i].to]=1;q.push(edge[i].to);}}}}return pre[t]!=-1;}void MCMF(){while(spfa(s,t)){int now=t;maxflow+=flow[t];mincost+=flow[t]*dis[t];while(now!=s){edge[last[now]].flow-=flow[t];edge[last[now]^1].flow+=flow[t];now=pre[now];}}}struct man1{int x,y;}man[105];struct home1{int x,y;}home[105];int main(){int cc,kk;while(~scanf(\"%d %d\",&cc,&kk)){getchar();mem(head,-1);mem(pre,-1);if(cc==0)break;cnt=0;maxflow=0;mincost=0;int num1=0,num2=0;char c;for(int i=1;i<=cc;i++){for(int j=1;j<=kk;j++){scanf(\"%c\",&c);if(c==\'m\'){man[++num1].x=i;man[num1].y=j;}else if(c==\'H\'){home[++num2].x=i;home[num2].y=j;}}getchar();}int p=num1;s=0;t=2*p+1;for(int i=1;i<=p;i++){addl(0,i,1,0);addl(i,0,0,0);addl(p+i,2*p+1,1,0);addl(2*p+1,p+i,0,0);for(int j=1;j<=p;j++){int d=abs(man[i].x-home[j].x)+abs(man[i].y-home[j].y);//cout<<i<<\" \"<<j+p<<\" \"<<d<<endl;addl(i,j+p,1,d);addl(j+p,i,0,-d);}}MCMF();cout<<mincost<<endl;}return 0;}
2、Dining POJ – 3281
题目大意：有N头牛 ，F种食物，D种饮料，给你每头牛喜欢的食物和饮料，问你最多可以满足几头牛的需要。
解题思路：难点即建图。建图时需要把牛拆开，把一头牛分为牛左 和 牛右，首先建立一个源点，从原点引出向食物的有向边，流量为1，在从食物引出向牛左的有向边，也就是与喜欢这种食物的牛相连，流量为1，然后再从牛左引出向牛右的有向边，流量为1，再从牛右引出向饮料的有向边，流量为1，最后将饮料引入汇点即可，最后跑一边最大流即可。
代码：
[code]#include <iostream>#include <cstdio>#include <fstream>#include <algorithm>#include <cmath>#include <deque>#include <vector>#include <queue>#include <string>#include <cstring>#include <map>#include <stack>#include <set>#define ll long long#define MOD 998244353#define INF 0x3f3f3f3f#define mem(a,x) memset(a,x,sizeof(a))#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);using namespace std;const int maxn= 2000 + 5; //点const int maxm= 2000 + 5; //边int n,m,cnt=0;int head[maxn];int dis[maxn];struct node{int e,v,nxt;}edge[maxm<<1];inline void addl(int u,int v,int w){edge[cnt].e=v;edge[cnt].v=w;edge[cnt].nxt=head[u];head[u]=cnt++;}bool bfs(){mem(dis,-1);dis[0]=0;queue<int>q;q.push(0);while(!q.empty()){int r=q.front();q.pop();for(int i=head[r];i!=-1;i=edge[i].nxt){int j=edge[i].e;if(dis[j]==-1&&edge[i].v){dis[j]=dis[r]+1;q.push(j);}}}return dis!=-1;}int dfs(int u,int flo){if(u==n)return flo;int detla=flo;for(int i=head[u];i!=-1;i=edge[i].nxt){int v=edge[i].e;if(dis[v]==(dis[u]+1)&&edge[i].v>0){int d=dfs(v,min(detla,edge[i].v));edge[i].v-=d;edge[i^1].v+=d;detla-=d;if(detla==0)break;}}return flo-detla;}int Dinic(){int ans=0;while(bfs()){ans+=dfs(0,INF);}return ans;}int main(){mem(head,-1);cnt=0;n=500;int N,F,D;scanf(\"%d %d %d\",&N,&F,&D);for(int i=1;i<=F;i++){addl(0,i+200,1);addl(i+200,0,0);}for(int i=1;i<=D;i++){addl(i+300,500,1);addl(500,i+300,0);}for(int i=1;i<=N;i++){int a,b,c;scanf(\"%d %d\",&a,&b);for(int j=1;j<=a;j++){scanf(\"%d\",&c);addl(c+200,i,1);addl(i,c+200,0);}addl(i,i+100,1);addl(i+100,i,0);for(int j=1;j<=b;j++){scanf(\"%d\",&c);addl(i+100,c+300,1);addl(c+300,i+100,0);}}int num=Dinic();cout<<num<<endl;return 0;}
