一、最大流

1.无源汇上下界可行流模型
（1）定义：给定一个无源点和汇点的流网络，每条边都有一个容量下界和一个容量上界。求出一种可行流。
（2）建图方式：对于每一个点，记指向这个点的有向边的容量下界之和是 $C_{1}$，从这个点出发的有向边的容量下界之和是 $C_{2}$。
STEP 1:把原图中的每一条边的上界减去容量下界，作为新图中这条边的容量。
STEP 2:若 $C_{1}>C_{2}$，则从源点 s 向这个点连一条有向边，边的容量是 $C_{1}-C_{2}$。
STEP 3:若 $C_{1}<C_{2}$，则从这个点向汇点 t 连一条有向边，边的容量是 $C_{2}-C_{1}$。
（3）可行流的存在性：在新图中求出最大流。若每条边的流量都等于它的容量，则原图中存在可行流；否则，原图中不存在可行流。
（4）可行流：在可行流存在的基础上，对于原图中每一条边，它的流量就是新图中这条边的流量再加上原图中这条边的容量下界。

2.有源汇上下界最大流模型
（1）定义：给定一个有源点和汇点的流网络，每条边都有一个容量下界和一个容量上界。求出它的最大流。
（2）建图方式：
STEP 1:从汇点 t 向源点 s 连一条容量是 $+\infty$ 的有向边，把流网络转化成一个无源汇上下界可行流模型；
STEP 2:新建一个源点 S 和一个汇点 T，并按照“1.”中的建图方式建图。
（3）可行流的存在性：在新图中从源点 S 向汇点 T 求出最大流。若每条边的流量都等于它的容量，则原图中存在可行流；否则，原图中不存在可行流。
（4）最大流：在可行流存在的基础上，在新图把从 t 向 s 的边删掉，再从源点 s 向汇点 t 做一遍最大流算法，直到新图中不存在从 s 到 t 的增广路径为止。新增加的流量再加上删边前从 t 到 s 的边流量即为最大流。

3.有源汇上下界最小流模型
（1）定义：给定一个有源点和汇点的流网络，每条边都有一个容量下界和一个容量上界。求出它的最小流。
（2）建图方式：同“2.”中的建图方式。
（3）可行流的存在性：同“2.”。
（4）最小流：与“2.”中类似。只是在第二次求最大流的时候，改成从 t 到 s 的最大流即可。最小流即为删边前从 t 到 s 的边流量减去第二次的最大流。

二、最小割

1.最大权闭合图模型
（1）定义：给定一个有点权、无边权的有向图。求图中的一个点权和最大的点集，使得整个图中不存在从点集中的点指向点集外的点的有向边。求出这个点权和。
（2）建图方式：
STEP 1:把原图中每条边的容量设为 $+\infty$；
STEP 2:从源点 s 向原图中每一个权值为正的点连一条有向边，边的容量是这个点的点权；
STEP 3:从原图中每一个权值为负的点向汇点 t 连一条有向边，边的容量是这个点的点权的相反数；
（3）最终点权和：记原图中所有权值为正的点的权值之和是 $s$，流网络中最小割的容量是 $f$，则答案是 $s-f$。
（4）最终点集：在残留网络中从源点出发，沿着所有容量大于 $0$ 的边搜索，搜到的所有点。

2.最大密度子图模型
（1）定义：给定一个无点权、无边权的无向图。在图中选择一个点集 $V’$ 和一个边集 $E’$，满足 $E’$ 中的所有边的端点全部都在 $V’$ 中，使得 $|E’|\div |V’|$ 的值最大。求出这个最大值。
（2）方法：令 $|E’|\div |V’|\leq g$，则 $|E’|-g|V’|\leq 0$。可二分找出 $g$ 的值，然后最大化 $|E’|-g|V’|$ 的值。（3）（4）（5）均考虑每一次二分时 $|E’|-g|V’|$ 的值。
（3）建图方式：
STEP 1:令 $d_{i}$ 表示点 $i$ 的度数。从原图中每一个点向汇点连一条有向边，边的容量是 $2g-d_{i}+U$，使得所有边的容量都是正数。
STEP 2:从源点向原图中每一个点连一条有向边，边的容量是 $U$。
STEP 3:保留原图中每一条无向边（建两条有向边），边的容量是 $1$。
（4）最终答案：记原图中点的个数是 $n$，最小割的容量是 $f$，则答案是 $\dfrac{U\times n-f}{2}$。
（5）最终点集和边集：在残留网络中从源点出发，沿着所有容量大于 $0$ 的边搜索，搜到的所有点和边。

3.二分图的最小点权覆盖集模型
（1）定义：给定一个有点权、无边权的二分图，其中所有点权非负。在图中选择一个点集，满足图中每一条边至少有一个端点在点集中，使得点集中所有点的权值之和最小。求出这个最小值。
（2）建图方式：
STEP 1:把原图中每一条边的容量设成 $+\infty$；
STEP 2:从源点 s 向二分图左部的每一个点连一条有向边，边的容量是对应的点权；
STEP 3:从二分图右部的每一个点向汇点 t 连一条有向边，边的容量是对应的点权。
（3）最终点权和：流网络中最小割的容量。
（4）最终点集：在残留网络中从源点出发，沿着所有容量大于 $0$ 的边搜索，搜到的所有点构成点集 $S$，未搜到的点构成点集 $T$。枚举所有边，若一条边起点在 $S$ 里、终点在 $T$ 里，则这条边的端点一定有一个是 s 或 t ，另一个就是所求点集中的一个点。这样的所有点构成点集。

4.二分图的最大点权独立集模型
（1）定义：给定一个有点权、无边权的二分图，其中所有点权非负。在图中选择一个点集，满足点集中任何两点之间不存在边，使得点集中所有点的权值之和最大。求出这个最大值。
（2）建图方式：同“3.”中的建图方式。
（3）最终点权和：记所有点权和是 $s$，最小权点覆盖集的点权和是 $a$，则答案是 $s-a$。
（4）最终点集：即最小点权覆盖集的补集。