最大流的入门题,第一次写了下ek算法,用了邻接矩阵。
EK算法的复杂度为O(n*m^2)
代码:
//EK算法求最大流问题二维数组实现
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#define INF 10000
#define maxn 205
using namespace std;
int n,m;
int path[maxn][maxn],pre[maxn],flow[maxn];
int vis[maxn];
int min(int x,int y)
{
return x<y?x:y;
}
int bfs()
{
memset(pre,-1,sizeof(pre));
memset(flow,INF,sizeof(flow));
memset(vis,0,sizeof(vis));
......
阅读全文