前言
如果还没有学过最大流,。
本文用到了优化的 \(SPFA\) , 。
思路
对于满足最大流合法的流函数可能有很多,但加上边的单位花费,则方案会减少很多。
实质上是在 \(Edmond-Karp\) 算法上进行改进。
\(Edmond-Karp\) 算法是对于残量网络上仅找到 \(1\) 条增广路进行增广。
而求最小费用最大流只需要在寻找增广路的过程中寻找花费最小的增广路。
建图
需要包含四个信息:终点节点编号,边的容量,边的花费,相反的边的编号。
struct Node {
int to, val, cost, rev;
Node() {}
Node(int T, int L, int C, int R) {
to = T;//终点节点编号
val = L;//边的容量
cost = C;//边的花费
rev = R;//相反的边的编号
}
};
确定增广路径
由 \(SPFA\) 实现,若不存在增广路径,则停止增广。
增广
在 \(SPFA\) 的过程中记录这条最短路路径编号,并记录这条路上的最小剩余容量。
用一个 \(while\) 循环寻找这条路径,并且直接记录这条路径的花费即可。
C++代码
#include
看看自己做对没有吖