最小费用最大流算法

最小费用最大流算法

原理

问题：网络中有源点（起点）和汇点（终点），每条边有流量上限和单位流量费用。求：

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