一、定義與定理
最小費用最大流：設G是以s為源t為匯的網絡，c是G的容量，b是G的單位流量費用，且有b[i][j] = -b[i][j]，f是G的流，則b(f)=∑(fij*bij)，(i, j)∈E(G) 且fij>0。最小費用最大流問題，就是求網絡G的最大流f且使費用b(f)最小。這樣的流稱為最小費用最大流。
二、算法思想
用Ford-Fulkerson算法的思想，不斷地在殘留網絡中尋找增廣路，只不過這個增廣路是當前網絡中s到t的以單位流量費用為權的最短路，對這條增廣路進行操作。由于費用有負值，建議用SPFA算法。
三、算法介紹
描述：
1 MCMF(G, s, t)
2 for each edge(u, v) in E(G)
3 do f[u, v] = 0
4 f[v, u] = 0
5 while exists a path p from s to t in Gf and p is the shortest path
6 do cf(p) = min{cf(u, v) : (u, v) in p}
7 for each edge(u, v) in p
8 do f[u, v] = f[u, v] + cf(p)
9 f[v, u] = - f[u, v]
實現：
1
mcmf()
2
{
3
while(true)
4
{
5 for(int i=1; i<=n+m+1; i++)
6 d[i] = MAX;
7 d[s] = 0;
8 spfa(); //p中存有該點的前繼點
9 if(p[t] == -1) //表示已無增廣路
10 break;
11 int minf = INT_MAX;
12 int it = t;
13 while(p[it] != -1)
14 {
15 minf = min(minf, c[p[it]][it] - f[p[it]][it]);
16 it = p[it];
17
}
18 it = t;
19 while(p[it] != -1)
20 {
21 f[p[it]][it] += minf;
22 f[it][p[it]] = -f[p[it]][it];
23 it = p[it];
24 }
25 }
26
}
三、算法示例
POJ 2516 解題報告
posted on 2009-06-30 22:29
Icyflame 閱讀(5847)
評論(0) 編輯 收藏 引用 所屬分類:
圖論