最小费用流bellman-ford算法总结

liuzhan214

于 2016-07-30 10:59:18 发布

阅读量3.6k

点赞数 2

分类专栏：曾经水过的题

本文链接：https://blog.csdn.net/liuzhan214/article/details/52071366

版权

本文探讨了最小费用流问题，强调在寻找流为F时如何确保最小费用。通过引入费用概念，使得最大流问题复杂化。为解决此问题，采用贪心策略，利用残余网络中的最短路径来逐步增加流量并降低费用。文章指出，借助bellman-ford算法，可以在存在负权边的环境中找到最短路，从而实现最小费用流的计算。

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

最小费用流问题是寻找流为F时的最小费用，普通的最大流中边只有流量限制，而在费用流中还加上了费用，为保证过程可逆和正确性残余网络中的负权边是原边费用的相反数，求解此类问题的方法依然是贪心，我们在残余网络上总是沿着最短路增广，这样可以保证在当前流量下，取得最小的费用（权值为费用），一直贪心下去，直到F减为0，这里有一个问题，F能否减到0呢，答案是肯定的，考虑最大流算法，我们总是能从0扩展到任意流（流不大于最大流），相应地，我们总是能从F沿着原路退到0。

以下是最小费用流的实现，因为残余网络中存在负权边，所以使用bellman-ford算法求解最短路。

#include <vector>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_V = 1005;
const int INF = 0x3f3f3f3f;
struct Edge{
    int to,cap,cost,rev;
    Edge(int t,int c,int co,int r):to(t),cap(c),cost(co),rev(r) {}
};
vector<Edge> G[MAX_V];
int V;
int prevv[MAX_V],preve[MAX_V];
int dist[MAX_V];

void add_edge(int from,

最低0.47元/天解锁文章