最基础的増广路、残流网的算法思想一定要非常清楚,Dinic,SAP基于増广路的思路去优化的。

记录一下网络流的建模常见基本套路。

最大流最小割定理

结论:对于任一个网络流图来说,其最大流一定是小于等于最小割的。

最大权闭合子图

结论:最大权闭合子图的权值等于所有正权点之和减去最小割
首先建立源点s和汇点t,将源点s与所有权值为正的点相连,容量为权值;
将所有权值为负的点与汇点t相连,容量为权值的绝对值;权值为0的点不做处理;同时将原来的边容量设置为无穷大。
例题:hiho1398

最小路径覆盖

进行前驱和后继的匹配,也就是二分图的最大匹配。

二分图多重匹配

同学可以参加一些项目,一个项目需要多个同学参加,是否所有项目都能被满足。
建立源点和同学相连,容量是该同学可参加的项目数;
建立汇点和项目相连,容量是该项目需要的同学数;
每个同学对于他可以参加的项目之间有一条边,容量是1;
例题:hiho1393