/**
一个多月没碰,感觉忘完了……
最小费就是有多条路可以满足最大流量的情况下所需要的最小费用
把费用改成相反数或改下spfa()的松弛就可最大费了
比如:从北京到上海运送一批货物,给出中间经过每条路线上对每辆车的收费,以及
每条路一次允许经过的车的数量,求一次性从北京到上海送尽可能多的货物情况下的最
小费用,当然中间经过的路线用二维数组即可表示,还有每条路的费用
则s 为北京, t 为上海, 带下面的模板即可
把问题转换成这个模型才是解决问题的关键,模板谁都会噢
*/
int cap[Max][Max], pre[Max], cost[Max][Max];
int que[Max], vis[Max], ans;
bool spfa(int s, int t) {
int i, head = 0, tail = 1;
for (i=0; i<=n; i++) {
dis[i] = inf;
vis[i] = false;
}
dis[s] = 0;
que[0] = s;
while (tail != head) {
int u = que[head++];
vis[u] = true;
for (i=0; i<=n; i++) { //n+1为点的个数
if (cap[u][i] && dis[i] > dis[u] + cost[u][i]) { //每次挑最小费用的路径
//这变成 < 即为最大费
dis[i] = dis[u] + cost[u][i];
pre[i] = u; //记录增广路径
if (!vis[i]) {
vis[i] = true;
que[tail++] = i;
if (tail == max)
tail = 0;
}
}
}
vis[u] = false;
if (head == Max)
head = 0;
}
if (dis[t] < inf)
return true;
return false;
}
void end(int s, int t) {
int i, sum = inf;
for (i=t; i!=s; i=pre[i])
sum = min(sum, cap[pre[i]][i]);
for (i=t; i!=s; i=pre[i]) {
cap[pre[i]][i] -= sum;
cap[i][pre[i]] += sum;
ans += cost[pre[i]][i]*sum;
}
}
int main()
{
//cap为源点汇点对应边得流量, cost 两边间的费用
//cost赋值 与源点汇点连接的cost 赋为0, cost[i][j] = a; cost[j][i] = -a;
//设源点为 s 汇点为 t
//调用:
ans = 0;
while (spfa(s, t))
end(s, t);
return 0;
}
收藏于 2012-01-08
来自于百度空间