这个算法是基于FF方法，就是通过不断求残余网络的增广路来增广流量，直到找不到增广路为止。注意：每次找到增广路以后都要更新原网络。EK算法通过BFS寻找源S到汇T的一条最短路径，因此时间复杂度是O(VE^2).
模板代码如下：
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#define MAX 1000
using namespace std;
int res[MAX][MAX];
int vis[MAX], pre[MAX];
queue<int>q;
int n;
bool bfs(int s, int t)
{
int p;
memset(vis, , sizeof(vis));
memset(pre, -, sizeof(pre));
while(!q.empty() q.pop();
q.push(s);
vis[s] = ;
while(!q.empty())
{
p = q.front();
q.pop();
for(int i = ;i <= n;i ++)
{
if(!vis[i] && res[p][i] > )
{
pre[i] = p;
vis[i] = ;
if(i == t)
return true;
q.push(i);
}
}
}
return false;
} int EdmondKarp(int s, int t)
{
int flow = , d, i, u;
while(bfs(s, t))
{
d = << ;
u = t;
while(pre[u] != -)
{
d = min(d, res[pre[u]][u]);
u = pre[u];
}
u = t;
while(pre[u] != -)
{
res[pre[u]][u] -= d;
res[u][pre[u]] += d;
u = pre[u];
}
flow += d;
}
return flow;
} int main(int argc, char const *argv[])
{
int m, u, v, w;
freopen("in.c", "r", stdin);
while(cin >> n >> m)
{
memset(res, , sizeof(res));
for(int i = ;i < m;i ++)
{
cin >> u >> v >> w;
res[u][v] += w;
}
int ans = EdmondKarp(, n);
cout << ans << endl;
}
return ;
}