待补全 qwq

最大流(Dinic 算法)

代码

模板:luogu3376_dinic.cpp loj101_dinic_struct.cpp
(数组写法在 loj 会 TLE,用 vector 结构体写在 loj 上快了五六倍。。)

最小费用最大流

参考:最小费用最大流 - riteme.site

问题

给定网络中,每条边 $e = (u, v)$ 有容量 $cap(u, v)$ 和单位流量的费用 $cost(u, v)$,要求最大化流量
$$f= \sum_{(u, v)\in E}flow(u, v)$$
同时最小化流的费用
$$w= \sum_{(u, v)\in E}flow(u, v)cost(u, v)$$
这样的流称为网络的最小费用最大流。

增广路算法

结论:网络中已有最小费用流(同流量的流中费用最小)时,沿残量网络中各边费用之和最小的增广路增广后,所得流仍为最小费用流。
算法过程:从零流开始不断沿残量网络中各边费用之和最小的增广路增广,当不存在增广路时,所得流为原网络的最小费用最大流。

代码

照着 Pepcy_Ch 的代码 写的:loj102_mcmf_all_struct.cpp