网络流最大流 Edmonds-Karp 增广路算法

本文主要是介绍网络流最大流 Edmonds-Karp 增广路算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

EK算法的思路非常的简单，就是一直找增广路径（BFS），假如有，记录增广路的最小值k，ans +=k ，并更新网络的值（要用反向边）。

贴模板：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define N 10005
#define M 200005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,s,t,cnt=1,head[N],incf[N],pre[N],maxflow; 
bool vis[N];struct Node{int to,nxt,val;
}edge[M];void add(int x,int y,int z)
{cnt++;edge[cnt].to=y;edge[cnt].nxt=head[x];edge[cnt].val=z;head[x]=cnt;
}bool bfs()//寻找增光路 
{memset(vis,0,sizeof vis);queue<int> q;q.push(s);  vis[s]=1;  incf[s]=inf;while(q.size()){int u=q.front(); q.pop();for(int i=head[u];i;i=edge[i].nxt){if(edge[i].val){int v=edge[i].to;if(vis[v]) continue;incf[v]=min(incf[u],edge[i].val);pre[v]=i;            //记录前驱，便于找到最长路的实际方案q.push(v);  vis[v]=1;if(v==t) return true; }}}return false;
}void update()//正向边-流，反向边+流 
{int x=t;while(x!=s){int i=pre[x];edge[i].val-=incf[t];edge[i^1].val+=incf[t];x=edge[i^1].to;}maxflow+=incf[t];
}int main()
{scanf("%d%d%d%d",&n,&m,&s,&t);for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z); add(y,x,0);//成对储存 }while(bfs()) update();printf("%d",maxflow);return 0;
}

这篇关于网络流最大流 Edmonds-Karp 增广路算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---