学艺不精，这么久才搞出来。
学东西，还是要看透本质。
最小割
设原图点集为V = {1..n}
建立2分图(X-Y)，X为点集{n..2*n+1}，Y为点集{1..n}
设s为源点, t为汇点
对任意的v∈X, e(s,v)边权为w-， 对任意的v∈Y, e(v,t)边权为w+, 若原图存在i->j 则在新图中 e(i,j+n) = ∞
跑出来的最大流（最小割）就是最小代价。
正确性证明：
1 割对应可行解：
可以看出原图中存在的每一条边都在网络流图G中有一个 e(xi, yj) 对应，要将原图中的每条边删除，即对应着在网络流图G中将每条边 e(xi, yj) 相关联的操作xi、yj执行至少一次。
首先，我们可以看到在求出来的最小割中，边e(xi, yj)一定不在其中，因为边e(xi, yj)边权为无穷大，这是显而易见的。因此割边一定出现在{e|v∈V,e(s,v)>0},或者{e|v∈V,e(v,t)>0}当中。
那么，我们现在只要证明任意一个满足上述条件的割C(S, T)是一个可行解，即满足割边不在{e|e(u, v) = ∞}中的割。
在上述C(S, T)中，对于任意一个点u∈V-{s, t}，则我们有u或者属于S, 或者属于T,
因此对于每条边e(u, v)，则我们必有(u,v∈S) || (u,v∈T), 则我们会得到相应的割边e(v, t) || e(s, u)
则对应的每条边我们都有一个+或-的删除操作.
所以一个上述割, 一定对应一个可行解.
2 最小割满足上述割, 并且为最优解。
现在剩下了最后一个问题，求任意一个最小割割集：
跑完最大流以后，让我们来构造这个最小割割集C(S, T)。
初始，令S={s}
在残余网络R中，若e(u,v)>0，则称点u到点v可达。
BFS将所有从s可到达的点v并入S集，
即S={{s}U{残余网络R中从s可达的所有点v}}
则T=V-S
这样，我们就得到了一个最小割割集C(S, T)。
令u∈S, v∈T, 若在原图G中，e(u,v)>0，则e(u, v)为割边。
证明：
1 是S-T切割。
反证，如果t属于S，则s到t可达，则存在一条增光路，则跑出来的不是最大流。（根据最大流最小割定理。）
2 是最小切割
因为，最大流=最小切割。
