最小费用最大流 spfa() + ek()

本文探讨了如何解决最大流量最小费用问题,通过将费用改为相反数或调整SPFA算法的松弛过程,实现从北京到上海运送货物时的最优成本策略。文章详细介绍了问题转换方法及模板应用。

摘要生成于 C知道 ,由 DeepSeek-R1 满血版支持, 前往体验 >

/**
    一个多月没碰,感觉忘完了……

    最小费就是有多条路可以满足最大流量的情况下所需要的最小费用
    把费用改成相反数或改下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
来自于百度空间

以下是使用Java实现最小费用最大流的示例代码,使用了Edmonds-Karp算法和SPFA算法: ```java import java.util.Arrays; import java.util.LinkedList; public class MinCostMaxFlow { private int n, m, s, t, maxFlow, minCost; private int[] head, dis, pre, flow, vis; private Edge[] edges; private LinkedList<Integer> queue; public MinCostMaxFlow(int n, int m, int s, int t) { this.n = n; this.m = m; this.s = s; this.t = t; this.head = new int[n + 1]; this.edges = new Edge[m + 1]; this.dis = new int[n + 1]; this.pre = new int[n + 1]; this.flow = new int[n + 1]; this.vis = new int[n + 1]; this.queue = new LinkedList<>(); Arrays.fill(head, -1); } public void addEdge(int u, int v, int cap, int cost) { edges[m] = new Edge(u, v, cap, cost, head[u]); head[u] = m++; edges[m] = new Edge(v, u, 0, -cost, head[v]); head[v] = m++; } private boolean spfa() { Arrays.fill(dis, Integer.MAX_VALUE); Arrays.fill(vis, 0); dis[s] = 0; vis[s] = 1; flow[s] = Integer.MAX_VALUE; queue.add(s); while (!queue.isEmpty()) { int u = queue.poll(); vis[u] = 0; for (int i = head[u]; i != -1; i = edges[i].next) { int v = edges[i].v; if (edges[i].cap > 0 && dis[v] > dis[u] + edges[i].cost) { dis[v] = dis[u] + edges[i].cost; pre[v] = i; flow[v] = Math.min(flow[u], edges[i].cap); if (vis[v] == 0) { vis[v] = 1; queue.add(v); } } } } return dis[t] != Integer.MAX_VALUE; } public void minCostMaxFlow() { while (spfa()) { int u = t; maxFlow += flow[t]; minCost += dis[t] * flow[t]; while (u != s) { edges[pre[u]].cap -= flow[t]; edges[pre[u] ^ 1].cap += flow[t]; u = edges[pre[u]].u; } } } static class Edge { int u, v, cap, cost, next; public Edge(int u, int v, int cap, int cost, int next) { this.u = u; this.v = v; this.cap = cap; this.cost = cost; this.next = next; } } } ``` 使用方法如下: ```java // 创建一个最小费用最大流对象 MinCostMaxFlow mcmf = new MinCostMaxFlow(n, m, s, t); // 添加边 mcmf.addEdge(u, v, cap, cost); // 求解最小费用最大流 mcmf.minCostMaxFlow(); // 最大流量 int maxFlow = mcmf.maxFlow; // 最小费用 int minCost = mcmf.minCost; ``` 其中,`n`表示点的数量,`m`表示边的数量,`s`表示源点,`t`表示汇点,`u`、`v`、`cap`、`cost`分别表示边的起点、终点、容量和费用。
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值