以前只知道最小割就是最大流...网络流背个模板，没了

根本没有深入理解，最近写了一些题才知道自己很 $naive$

废话不多说，开始正题（假设大家都会网络流的代码，并且知道网络流在做什么）

首先最小割就是最大流（废话）

一条图的最小割中，一定有一些边，它们是满流的（如果不满流就不是最大流了）

不妨把这些边称作割边，显然，这些割边把图分成两个部分，一个与源点 $S$ 在同一个部分，一个与汇点 $T$在同一个部分

放图理解：

　　首先原图长这样：

　　然后一种最小割长这样（红色的是满流的边）：

我们把与 $S$ 在同一个部分的点集叫作 $S$割，与 $T$ 在同一个部分的点集叫作 $T$割

那么 $S$割 包括点 ${1,2,4}$， $T$割 包括点 ${3,5,6,7}$

注意满流边不一定是割边，比如这个图：

割边可以是 $(S,1)$ 或者是 $(1,2)$ ，显然对于这种有多解的最小割随便一种都合法

如果把边看成 $(u,v,cost)$（从 $u$ 到 $v$，花费（流量）是 $cost$ ），考虑最小割的实际意义

就是把点集分成 $S$割 和 $T$割 的最小花费

（请先好好理解以上理论再看下去$qwq$）

接下来考虑最小割模型中的三种边：

1. $(S,u,cost)$，意思是 如果 $u$ 在 $T$割（此边满流），那么要产生 $cost$ 的代价

2. $(u,T,cost)$，意思是 如果 $u$ 在 $S$割（此边满流），那么要产生 $cost$ 的代价

再进一步考虑一条边 $(u,v,cost)$ 的实际意义：如果把 $u$ 给 $S$割， $v$ 给 $T$割（此边满流），那么会产生 $cost$ 的代价

扩展一下，对于一条边 $(u,v,cost)$ ，如果 $cost$ 是正无穷 那么这个边的意思是什么？

光速回答，$u$ 和 $v$ 不能在同一个割集！

好像很有道理，因为这个边不可能满流，所以 $u$，$v$ 必须在同一个割集里

但是注意，边是有向边，从 $u$ 到 $v$！如果 $u$ 在 $T$割，$v$ 在 $S$割 也是合法的

所以这条边的真正意思是 ，如果 $u$ 在 $S$割，那么 $v$必须在 $S$割

（休息一下，一定要真正理解边的意义$qwq$）

更近一步，对于一种题型：有 $n$ 个点，每个点有一个价值 $val$ （可能为负），点之间有一些限制关系 $(x,y)$（选了点 $x$ 必须选点 $y$），并且保证对于任意限制 $(x,y)$， $val[x]>0,val[y]