一、定义与定理
最小费用最大流：设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 阅读(5782)
评论(0) 编辑 收藏 引用 所属分类:
图论