2 qq11111qqwowo qq11111qqwowo 于 2014.08.19 21:56 提问

关于网络流的算法真是混乱了

有人说Edmonds-Karp算法就是SAP算法,又有的说Edmonds-Karp算法就是Ford-Fulkerson算法,求解释这几个算法到底哪个是哪个?顺便问一下网络流的算法哪个是最快的。附上代码一份。我都不知道这个到底是哪个算法。`#include
#include
#include
#include
using namespace std;
const int maxn = 201;

int edges[maxn][maxn];
int n,m;
int ans;
int father[maxn];
bool visited[maxn];

void ford_fulkerson()
{
ans = 0;
while(1)
{
queue Q;
memset(father,-1,sizeof(father));
memset(visited,0,sizeof(visited));
visited[0] = true;
Q.push(0);
while( !Q.empty())
{
int now = Q.front();
Q.pop();
if(now == m-1)
break;
for(int i = 0; i < m; i++)
{
if(!visited[i] && edges[now][i])
{
father[i] = now;
visited[i] = true;
Q.push(i);
}
}
}
if( !visited[m-1] )
break;
int minimal = 1000000000;
for(int i = m-1; i ; i = father[i])
{
if(minimal > edges[father[i]][i])
minimal = edges[father[i]][i];
}
for(int i = m-1; i ; i = father[i])
{
edges[father[i]][i] -= minimal;
edges[i][father[i]] += minimal;
}
ans += minimal;
}
printf("%d\n",ans);
}
int main()
{
freopen("input.txt","r",stdin);
while(~scanf("%d%d",&n,&m))
{
int f,t,w;
memset(edges,0,sizeof(edges));
for(int i = 0; i < n; i++)
{
scanf("%d%d%d",&f,&t,&w);
edges[f-1][t-1] += w;
}
ford_fulkerson();
}
return 0;
}
`

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!