Posted on 2009-08-29 13:39
reiks 閱讀(751)
評論(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;
}