C++费用流算法详解（从零开始掌握最小费用最大流实现）

什么是费用流？

在网络流模型中，每条边除了有容量限制外，还可以附加一个“单位流量的费用”。我们的目标是：在从源点（source）到汇点（sink）输送尽可能多流量的同时，使得总费用最小。

例如：物流公司要从仓库（源点）向多个门店（汇点）运送货物，每条运输路线有最大运力（容量）和每单位货物的运费（费用）。如何安排运输方案，既能送最多货，又花最少钱？这就是典型的最小费用最大流问题。

算法核心思想

费用流算法通常基于 最短路径增广 的思想：

1. 每次在残量网络中寻找一条从源点到汇点的 最小费用路径（即单位流量总费用最小的路径）；
2. 沿着这条路径尽可能多地推送流量（受路径上最小剩余容量限制）；
3. 更新残量网络和反向边的费用（反向边费用为负）；
4. 重复上述过程，直到无法再找到增广路径为止。

为了高效地找最小费用路径，我们使用 SPFA（Shortest Path Faster Algorithm） 或 Dijkstra（需处理负权边）。由于费用流中可能存在负权边（反向边），这里推荐使用 SPFA。

C++ 实现步骤详解

我们将使用邻接表存储图，并维护以下信息：

• to：边指向的节点
• cap：剩余容量
• cost：单位流量费用
• rev：反向边在邻接表中的索引

1. 定义图结构

struct Edge {    int to, cap, cost, rev;    Edge(int t, int c, int co, int r)         : to(t), cap(c), cost(co), rev(r) {}};const int INF = 0x3f3f3f3f;vector<vector<Edge>> graph;

2. 添加边（含反向边）

void add_edge(int from, int to, int cap, int cost) {    graph[from].emplace_back(to, cap, cost, graph[to].size());    graph[to].emplace_back(from, 0, -cost, graph[from].size() - 1);}

注意：反向边初始容量为 0，费用为负值，用于“撤销”流量操作。

3. 使用 SPFA 寻找最小费用路径

bool spfa(int s, int t, vector<int>& dist,            vector<int>& prevv, vector<int>& preve) {    int n = graph.size();    dist.assign(n, INF);    vector<bool> inq(n, false);    dist[s] = 0;    queue<int> q;    q.push(s);    inq[s] = true;    while (!q.empty()) {        int u = q.front(); q.pop();        inq[u] = false;        for (int i = 0; i < graph[u].size(); ++i) {            Edge& e = graph[u][i];            if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {                dist[e.to] = dist[u] + e.cost;                prevv[e.to] = u;                preve[e.to] = i;                if (!inq[e.to]) {                    inq[e.to] = true;                    q.push(e.to);                }            }        }    }    return dist[t] != INF;}

4. 主函数：最小费用最大流

pair<int, int> min_cost_max_flow(int s, int t) {    int flow = 0, cost = 0;    vector<int> dist, prevv, preve;    while (spfa(s, t, dist, prevv, preve)) {        int f = INF;        for (int v = t; v != s; v = prevv[v]) {            f = min(f, graph[prevv[v]][preve[v]].cap);        }        for (int v = t; v != s; v = prevv[v]) {            Edge& e = graph[prevv[v]][preve[v]];            e.cap -= f;            graph[v][e.rev].cap += f;        }        flow += f;        cost += f * dist[t];    }    return {flow, cost};}

完整使用示例

#include <iostream>#include <vector>#include <queue>#include <algorithm>#include <climits>using namespace std;// 上面定义的 struct Edge、add_edge、spfa、min_cost_max_flow 等代码放在这里int main() {    int n = 4; // 节点数（0~3）    graph.resize(n);    // 添加边：from, to, capacity, cost    add_edge(0, 1, 10, 1);    add_edge(0, 2, 5, 2);    add_edge(1, 2, 15, 1);    add_edge(1, 3, 10, 3);    add_edge(2, 3, 10, 1);    auto [max_flow, min_cost] = min_cost_max_flow(0, 3);    cout << "最大流量: " << max_flow << endl;    cout << "最小费用: " << min_cost << endl;    return 0;}

总结

通过本教程，你已经掌握了如何用 C++ 实现最小费用最大流算法。该算法广泛应用于物流调度、资源分配、任务匹配等实际场景。理解并熟练运用C++网络流实现技巧，将极大提升你在算法竞赛和工程开发中的竞争力。

记住关键点：构建残量网络、使用 SPFA 找最短费用路径、沿路径增广并更新反向边。多加练习，你就能轻松应对各类图论算法教程中的高级问题！

提示：在实际项目中，可考虑使用更高效的 Dijkstra + 势函数（Johnson）来避免负权边问题，进一步提升性能。