最小費用最大流算法

原理

問題：網絡中有源點（起點）和匯點（終點），每條邊有流量上限和單位流量費用。求：

1. 從源點到匯點的最大流量
2. 在流量最大的前提下，總費用最小

核心思想：在找增廣路時，選擇單位費用之和最小的路徑（使用SPFA找最短路）

實現步驟

1. 建圖：使用鏈式前向星存儲（含反向邊）
   • 正向邊：容量cap，費用cost
   • 反向邊：容量0，費用-cost
2. 算法流程：
   • Step 1：用SPFA找費用最短路（記錄路徑和最小流量）
   • Step 2：沿路徑增加流量，更新費用
   • Step 3：重復直到沒有增廣路
3. 結果：最大流量 = 所有增廣流量之和，最小費用 = 流量×路徑費用之和

C++ 模板

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;const int N = 5010, M = 50010, INF = 0x3f3f3f3f;struct Edge {int to, next, cap, cost;
} edges[M << 1];int head[N], cnt;
int pre[N], dis[N], flow[N];
bool vis[N];
int n, m, s, t;  // 點數、邊數、源點、匯點void init() {cnt = 0;memset(head, -1, sizeof head);
}void addEdge(int u, int v, int cap, int cost) {// 正向邊edges[cnt] = {v, head[u], cap, cost};head[u] = cnt++;// 反向邊edges[cnt] = {u, head[v], 0, -cost};head[v] = cnt++;
}bool spfa() {memset(dis, 0x3f, sizeof dis);memset