Posted on 2009-08-29 13:39
reiks 阅读(719)
评论(0) 编辑 收藏 引用 所属分类:
算法与数据结构
//Edmonds-Karp
//return the largest flow;flow[] will record every edge's flow
//n, the number of nodes in the graph;cap, the capacity
//O(VE^2)
#define N 100
#define inf 0x3f3f3f3f
int Edmonds_Karp(int n,int cap[][N],int source,int sink)
{
int flow[N][N];
int pre[N],que[N],d[N]; // d 是增广路长度，pre 记录前驱，que是BFS队列
int p,q,t,i,j;
if (source==sink) return inf;
memset(flow,0,sizeof(flow));
while (true)
{
memset(pre,-1,sizeof(pre));
d[source]=inf;
p=q=0, que[q++] = source;
while(p < q&&pre[sink]<0) // BFS 找路径
{
t=que[p++];
for (i=0;i<n;i++)
if ( pre[i]<0 && (j=cap[t][i]-flow[t][i]) ) // j取得残余路径值
pre[que[q++] = i] = t,d[i] = min(d[t], j);
}
if (pre[sink]<0) break; // 找不到增广路，退出
for (i=sink; i!=source; i=pre[i])
{
flow[pre[i]][i]+=d[sink]; // 正向流量加
flow[i][pre[i]]-=d[sink]; // 反向流量减
}
}
for (j=i=0; i<n; j+=flow[source][i++]);
return j;
}