关于我的网络流模板代码，可以在这里找到，喜欢就给个star吧。
网络流本质是一类特殊的线性规划，满足性质：
- 容量限制
- 流量平衡
第一步
首先，我们对于题目要确定网络流的类型，即使用最小割还是费用流。
- 若确定使用最小割，原题求最小代价，则直接设割掉的是需要选择的。若原题求最大收益，则设割掉的是不选择的，最后用总和减去最小割就是答案。
- 若确定使用费用流，在建模后需要考虑图的形状从而决定使用EK修改版还是zkw费用流。
捆绑模型
捆绑模型指一些点可以有一些选择方案，有一定的价值，同时一些点同时选择一些方案可以获得额外奖励。
- 二元组建模
我们根据需要割掉的边和对应的奖励建立不定方程组，解出不定方程的一组解（方便建模），即可按照这组解建模。
这样的建模方式要求$e+f\ge0$（见彭天翼论文），我们可以通过转化使其可以解决$e+f\le0$的情况。
这样的转化我们可以使$e+f\le0$时变成$e+f\ge0$，但要求原图是二分图。
若$a,b,c,d\le0$可以添加一个偏移量使其$\ge0$，最后再统一减去。
若对于多个点的捆绑，需要新建一个点控制这些多个点。
- 捆绑模型专用模型
对于奖励新建一个点，将其与捆绑的点连边。
经典例题
最大权闭合子图
对于一些这样的限制：选择了一些点必须要选择另一些点。
最大化总权和，这就是最大权闭合子图的模型。
经典例题
- CEOI2008 order（懒得写题解）
- NOI2009 植物大战僵尸（懒得写题解）
- 完美理论
离散变量模型
一些离散变量可以有一些取值，但离散变量间有偏序关系的限制。
如图，我们可以通过一个变量的取值，将例外一个变量限制在一段区间内（偏序限制）。
当然，我们需要对每一个变量取值都建$inf$的边进行限制。
经典例题
- HNOI2013 切糕
- Codechef DEC14 RIN
- BJOI2016 水晶
流量分配和匹配模型
流量分配包含的范围很广，表示通过一定的建模，将一定的流量分配到其它地方去。
这类模型一般还包括二分图匹配，路径覆盖，动态加点 等。
经典例题
- 圆桌问题
- SCOI2012 奇怪的游戏
- SDOI2010
- Codechef SEPT 12 PARADE
- CF277E Binary Tree on Plane
- CTSC1999 家园
- HNOI2007 紧急疏散
- SCOI2007 修车
- NOI2012 美食节
- WC2007 剪刀石头布
二维模型
一般原图是网格状，对行和列有限制。
一般的建图方式是建立二分图，一边是行一边是列，用连接所在行列的边表示对应格子的决策。
经典例题
- bsoj2311 宫廷守卫
流量平衡
流量平衡是费用流的模型。
利用每个点流入流量等于流出流量来满足等式。
因为费用流有限满足流最大，后满足费用的最值，故我们可以用如图的模型对入出度进行限制（保证$x’$流入流量等于$x$流出流量）。
应用1：混合图欧拉回路
给一个混合图，要你给无向边定向并求出欧拉回路。
先随便定向，建立超级源汇，流量平衡保证出入度平衡。
应用2：消负环
利用流量平衡模型，我们可以在保证入出度平衡的情况下，将负环全部消去（费用为负，最小费用最大流会尽可能满足）。
经典例题
上下界网络流
建立超级源汇，由下界计算与源汇连边的代价，用最大流增广自由流。
对于原图有源汇的需要建立后悔边（$t\rightarrow s$）。
经典例题
- POJ2396
一维模型
一般的建模方式是直接建立一条链：
$S\rightarrow x_1\rightarrow x_2\rightarrow x_3\rightarrow \cdots\rightarrow x_n\rightarrow T$
通过容量限制和流量平衡满足条件，利用费用求答案。
