这是个大工程，以后会不断补充。

最大流

最大流的建模，往往是把流量和题目要求的东西直接关联起来，是最简单直白的建模。最大流的模型有时候可以转化为二分图最大匹配。

拆点模型

P2472 [SCOI2007] 蜥蜴

网络流图中的点如果有流量限制，那么可以把一个点 $u$ 拆成入点 $u_1$ 和出点 $u_2$，$u_1$ 负责接收流量，$u_2$ 负责输送流量，$u1$ 向 $u2$ 连一条流量为点权的边即可。

分层图模型

P2754 [CTSC1999]家园 / 星际转移问题

网络流图中的点如果会“动”，那么不妨按时间分层建图，模拟时间流逝。

还有一类题比较特殊，要求最小层数。那么先判断无解，再不断加层直到满足条件即可。

最小路径覆盖模型

P2764 最小路径覆盖问题

正难则反，首先考虑让所有点都自成路径，然后考虑尽可能通过边来“合并”这些路径。

因为每个点只能在一条路径上，所以考虑拆点。把每个点 $u$ 拆成 $u_1$ 和 $u_2$，源点向 $U_1$ 连一条流量为 $1$ 的边，$u_2$ 向汇点连一条流量为 $1$ 的边，表示 $u$ 在路径上的前驱和后继只能有 $1$ 个节点。

然后对于每条边 $(x,y)$，从 $x_1$ 向 $y_2$ 连一条边，表示 $y$ 可以做 $x$ 的后继，$x$ 可以做 $y$ 前驱。

最后用 $n$ 减去最大流即可。

可以发现此时的图其实是一个二分图，所以可以用二分图最大匹配代替网络流。

流量平衡模型

见 网络流求最小费用特解（网络流解线性规划）学习笔记

危桥模型

P3163 [CQOI2014]危桥

往返 $a_n$ 次相当于是从 $a_1$ 到 $a_2$ 走了 $2a_n$ 次，$b$ 也一样，所以问题转化为：

有两组源汇点 $s1,t1$ 和 $s2,t2$，$s1\to t1$ 最多流 $a1$ 的流量，$s2\to t2$ 最多流 $a2$ 的流量，请判断能否满流。

若直接源点向 $s1,s1$ 分别连流量为 $a1,a2$ 的边，$t1,t2$ 向汇点连流量为 $a1,a2$ 的边然后判是否满流，可能会出现这种情况：

即所有满流的方案中都会有一部分流量从 $s1$ 流到 $t2$，一部分流量从 $s2$ 流到 $t1$，此时实际上是不存在合法方案的，但是这样建图却会认为可以满流。

解决方案很简单，我们交换 $s2,t2$，即从源点向 $t2$ 连流量为 $a2$ 的边，从 $s2$ 向汇点连流量为 $a2$ 的边，其余部分连边不变，再判断一次是否满流。若上图中的不合法情况必然出现，那么新图不可能满流；否则若新图上这种情况必定出现：

那么原图必定不可能满流。因为假若这两种情况同时出现，那么就可以这样流：

所以只要这两个图都能满流就证明原问题有解。

类似的，这种建模方法应该还能推广到有 $n$ 对源汇点的情况，通过固定一对源汇点，枚举剩下的源汇点的交换与否，跑 $2^{n-1}$ 次最大流，则原问题有解当且仅当每次都是满流。

最小割

从最小割角度建模也是一种比较常见的建模方式。

设点 $u$ 最终在源点 $S$ 所在的连通块则 $b_u=1$，否则 $b_u=0$。

基本模型

考虑最小割的数学定义：

• 边 $(S,x,a)$ 对答案的贡献为 $a\times (1-b_x)$；
• 边 $(x,T,a)$ 对答案的贡献为 $a\times b_x$；
• 边 $(x,y,a)$ 对答案的贡献为 $a\times b_x(1-b_y)$；

所以基本限制如下：

有 $n$ 个 01 变量 $b_i$，你需要确定每个 $b_i$ 的取值使得代价最小。

代价分为三类：

• 若 $b_i=0$，有代价 $w1_i$；
• 若 $b_i=1$，有代价 $w2_i$；
• 若 $b_i=1$ 且 $b_j=0$，有代价 $w3_{i,j}$；

基本模型如下：

给第 $i$ 个元素建一个点 $i$。

• 对于第一类限制，连边 $(S,i,w1_i)$；
• 对于第二类限制，连边 $(i,T,w2_i)$；
• 对于第三类限制，连边 $(i,j,w3_{i,j})$；

混合模型

相当于把基本模型中的 $S$ 换成别的点，流量不再由 $S$ 直接提供。

可以看成多层基本模型。

共同收益模型

P1361 小M的作物

诸如「对于所有 $u\in A$，若 $\sum b_u\not=|A|$ 则有代价 $w$」的情况，可以新建一个点 $u$，连接边：

• $(S,u,w)$；
• $(u,x,\inf)$，其中 $x\in A$；

同理，「对于所有 $u\in A$，若 $\sum b_u\not=0$ 则有代价 $w$」的情况也可以类似做，新建一个点 $u$，连接边：

• $(u,T,w)$；
• $(x,u,\inf)$，其中 $x\in A$；

建图是这样的：

切糕模型

P3227 [HNOI2013] 切糕

有 $n$ 个整数变量 $b_i$，第 $i$ 个变量取值范围 $[L_i,R_i]$。

代价分为两类：

• $b_i=x$ 时有代价 $W_{i,x}$；
• $b_i\ge x,b_j\ge y$ 时有代价 $W_{i,x,j,y}$；

直接看图吧：

混合模型

各种模型的流量都可以不由 $S$ 直接提供。

P8215 [THUPC2022 初赛] 分组作业 | 题解