最大流
Dinic
建图时必须要建一条流量为0的反向边
#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[n]!=-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，花费是相反数。
#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，跑一遍最小花费最大流即可。
代码：
#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，最后将饮料引入汇点即可，最后跑一边最大流即可。
代码：
#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[n]!=-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;
}