最小费用最大流 | caojiangxia

[caojiangxia]

https://caojiangxia.github.io/MinCostMaxFlow/#more

费用流最小费用最大流从上次讲最大流已经过了一段时间了，这次我们讲一讲最大流的另一种特殊情况，费用流，其全名应该是最小费用最大流。这个在算法竞赛中十分常用，因为只要牵扯到需要拆点和拆边的情况下，我们都需要用费用流，而这种操作实在是不能在普通了。 问题定义在这里，问题相比最大流要稍微复杂一些，给定我们一个图$G$，和图中一些边$E$,但是其中每条边有两种属性： 该条边的最大流量 该条边每通过一个流量