update：2021-04-13 21:49 根据RuSun的建议，更改了解题步骤
请确保你知道网络流、最大流、最小割
鉴于最小割模型不宜想到，且变化多端，特出此笔记
1.应用
最小割常用来求最小代价，以及最大收益（满足一定条件才能获得）
最小割的复杂度与最大流相同，为$O(n^2m)$
由于模板没有可考察的，所以难点一般在建图上。
2.模型
0） 前言
最小割求的是最小代价，即不选某条边的代价
满流表示的是割断该条边，并支付该代价
未满流的边，一般视为0
最小割求的是边的割，如果是点的代价，则使用拆点法
对于不能割断的边，将其流量设为 $+\infty$
1） 最小代价型
T1：
P1345 [USACO5.4]奶牛的电信Telecowmunication
这是一道典型的 01 最小代价问题，从入点到出点都是1的代价。
将每个点拆为入点和出点，之间的代价为1
每条边的代价为 $+\infty$，即不能割断。
不贴代码了，自己建图最大流就可以了。
T2：
这是一道多代价问题，不只是 1 的代价
同样要用到拆点法，入点与出点的连边为轰炸该点的炸药数，
注意，如果是本身是障碍物的话，相当于轰炸为0代价，在网络流中可以直接掠过。
从敌军位置向起点连边，从边界向汇点连边，就可以了。
2） 最大收益类
其实最大收益类都可以转化为最小代价类。
为什么单独拿出来说呢？因为很多时候，看不出来是最小割。
看几道题理解一下。
T1：
很多同学看到“最大和”，迫不及待地要用最大流。
但这道题，如果是最大流的话，会使图的规模增长一个数量级，并且杂乱无章。
（所以讲一下还是有必要的）
我们考虑应该不要哪些点。
回归割的定义，任意一条从 s 到 t 的路径，必有一条是割边。
我们将有关联的点全部连在一起，再将这些点分别接到源汇点上，会发现，任意一条边，要么左边满流（取其代价），要么右边满流
进一步观察题目，挖掘性质，我们可以发现，可将原图分为两部，相邻的点在不同部。
我们就可以发现，再将两部的点分别连到源汇点，就满足了上面的性质！
这样建图就可以了，用最大流跑。
T2：
输出里直接说到“最大利润”，所以是最大收益的题目。
我们考虑哪些实验不要，以及需要支付的费用。
先将每个实验与源点连边，接着与需要的配置连边$+\infty$，然后把配置与汇点连边。
挖掘性质：任意一条从 s 到 t 的路径，都会经过一个实验和配置。
要么实验满流（既不选），要么配置满流（即支付该费用）。
满足原问题的性质。
T3：
这道题与上道题类似，只不过多了一个租的环节。
分析上一题，发现相当于是租的费用为 $+\infty$，这道题，改为对应代价即可。
每一部分，要么不选工作，要么对应边满流（即租），要么买。
T4：
这道题提到，$-1000 \leq v(x) \leq 1000$，即可能为负。
我们可以把负点看做是代价，并将联系正负的分别与源汇点连边。
注意，负点不是收益，而是代价，该点没有满流代表不选该点
可以发现，要么正的满流（即不看），要么中间断开（即支付不看的代价），要么从负点断开（即支付看他的代价）。
详细证明参见 这篇博客
T5：
这是最能体现最小割通法的题目了。
按照先前的思路，就会发现牵扯过多，而不好建图。
这时我们采取的策略是：
先将所有的利益加进来，在将不能共存的状态连边（或者一定的费用），将连边的端点分别以一定代价连边源汇点。
按照这个思路，几乎可以秒杀该题。
将所有利益加起来，然后将 $same_art$ 与几个 $science$ 连边，$same_science$ 同理。
将带 $art$ 的与源点连边，其余的与汇点连边，用总收益减最小割即可。
3） 总结
我们可以用最小割解决问题，都用上面的策略建图即可。
3. 解题步骤
判断是不是最小割问题。
判断是不是最大收益类，如果是，先将收益加起来。
- 如果是最大收益类，就将不能共存的点连接起来。
- 如果是最小代价类，就将两点必须有至少其一的点连接起来。
- 跑最小割即可。
注意：这两类一般只能处理二分图的形式的题，除了一些明显的最小割问题
没有总结到的，请在评论区提出，我会按时回复。
希望对你有所帮助。