qq11111qqwowo 2014-08-19 13:56 采纳率: 0%
浏览 1310

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

有人说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;
}
`

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥50 安装pyaudiokits失败
    • ¥15 计组这些题应该咋做呀
    • ¥60 更换迈创SOL6M4AE卡的时候,驱动要重新装才能使用,怎么解决?
    • ¥15 让node服务器有自动加载文件的功能
    • ¥15 jmeter脚本回放有的是对的有的是错的
    • ¥15 r语言蛋白组学相关问题
    • ¥15 Python时间序列如何拟合疏系数模型
    • ¥15 求学软件的前人们指明方向🥺
    • ¥50 如何增强飞上天的树莓派的热点信号强度,以使得笔记本可以在地面实现远程桌面连接
    • ¥20 双层网络上信息-疾病传播