题目描述
求网络中的最大流。
样例
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
50
算法1
(dinic) $O(n^2\times m)$
Dinic
模版即可。
若有不会网络流/想学网络流的同学,这里推荐一篇dalao的blog。
C++ 代码
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
struct edge{
int to,flow,nxt;
}s[410];
int ls=2,head[210];
void link(int a,int b,int fl){
s[ls].to=b;s[ls].flow=fl;
s[ls].nxt=head[a];head[a]=ls++;
}
int dis[210];
queue<int>q;
int n;
int bfs(int u,int t){//bfs在残量图上重新分层
for(int i=0;i<=n;i++) dis[i]=0;
while(!q.empty()) q.pop();
q.push(u);dis[u]=1;
while(!q.empty()){
u=q.front();q.pop();
if(u==t) return 1;
for(int i=head[u],y;i;i=s[i].nxt)
if(!dis[y=s[i].to]&&s[i].flow){
dis[y]=dis[u]+1;
q.push(y);
}
}
return 0;
}
int dfs(int u,int t,int flow){//dfs求当前节点到汇点的最大流
if(u==t) return flow;
int res=flow,_flow;
for(int i=head[u],y;i;i=s[i].nxt)
if(s[i].flow&&dis[u]+1==dis[y=s[i].to]){
_flow=dfs(y,t,min(res,s[i].flow));
if(!_flow) dis[y]=0;
res-=_flow;
s[i].flow-=_flow;
s[i^1].flow+=_flow;
}
return flow-res;
}
int dinic(int s,int t){//直到残量图不连通
int maxf=0;
while(bfs(s,t)) maxf+=dfs(s,t,2000000000);
return maxf;
}
int main(){
int m,a,b,c;
while(scanf("%d%d",&m,&n)!=EOF){
if(n==0) break;
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
link(a,b,c);link(b,a,0);
}
printf("%d\n",dinic(1,n));
ls=2;
for(int i=0;i<=n;i++) head[i]=0;
}
return 0;
}
dalao
dalao
66666