网络流是一个适用范围极广的模型相关的算法也很多，大体分为最大流、最小割、费用流三类

对于网络流类型的题来说，一般根据题意分析后建出图后，套用相关模版即可解决问题。

关于网络流的基本概念与建模技巧：

求最大流算法分为两类一种是增广路算法，一种是预留推进算法

增广路算法，常用的有时间复杂度 O(n*m*m) 的 FF 算法、EK 算法上界为 O(n*n*m) 的 Dinic 算法，以及对 Dinic 进行改进的 ISAP 算法；压入与重标记算法又称预留推进算法其时间复杂度为 O(n*n*m)

求最大流的最小割时，根据最大流最小割定理可以在求最大流的过程中求出最小割，一般常用的是 Dinic 算法

若网络流的图是一个平面图，那么可以将其转为对偶图然后跑最短路算法

若要求最大权闭合子图，可以转为最小割问题然后利用 Dinic 来解决

若要求最大密度子图，那么需要利用 01 分数规划来分析从而转换模型

一个网络流图中最大流的流量是唯一的，但是达到最大流量时每条边上的流量分配是不唯一的。 

若给网络流图中的每条边都设置一个费用 cost表示单位流量流经该边时会导致花费 cost，那么在这些流量均为最大流的流量分配 f 中存在一个鋶量总花费最小的最大流方案。

求解最小费用最大流最常用的算法是基于 SPFA 的 MCMF 算法：

除以上两种求费用流的方法外还有一种更为高效的费鼡流算法，即 zkw 费用流：

除例题外可参考 Edelweiss 的《网络流建模汇总》，具体内容：

1. 狼抓兔子（HYSBZ-1001）(平面图转对偶图)：

1. 最小费用最大流（洛谷-P3381）(zkw费鼡流)：