蒟蒻网络流什么都不懂一上来就这么多概念要疯了
一一讲一下最小割定理之类的东西
搬运这里大佬原博
例题洛谷题
网络流24题（洛谷读入神坑。。。）
以下内容参考 胡伯涛 《最小割模型在信息学竞赛中的应用》，感谢他为我们提供这么优秀的论文。
这道题中，实验依赖于仪器，而实验和仪器都有权值，且仪器为负，实验为正。
这里闭合图的概念就很好引出了。在一个图中，我们选取一些点构成集合，记为V，且集合中的出边(即集合中的点的向外连出的弧)，所指向的终点(弧头)也在V中，则我们称V为闭合图。最大权闭合图即在所有闭合图中，集合中点的权值之和最大的V，我们称V为最大权闭合图。
例图
上图中闭合图有
{5}、{2,5}、{4,5}
{2,4,5}、{3,4,5}
{1,2,3,4,5}、{1,2,4,5}
最大权闭合图为{3,4,5}。
针对本题而言，我们将实验与仪器间连一条有向边，实验为起点(弧尾)，仪器为终点(弧头)。则如果我们选择一个闭合图，那么这个闭合图中包含的实验所需要的仪器也最这个闭合图里。而最大权闭合图即为题目的解。
了解了最大权闭合图的概念，接下来我们就需要知道如何求最大权闭合图。
首先我们将其转化为一个网络(现在不要问为什么,接下来会证明用网络可以求解)。构造一个源点S，汇点T。我们将S与所有权值为正的点连一条容量为其权值的边，将所有权值为负的点与T连一条容量为其权值的绝对值的边，原来的边将其容量定为正无穷。
此为转化图
首先引入结论，最小割所产生的两个集合中，其源点S所在集合(除去S)为最大权闭合图，接下来我们来说明一些结论。
- 证明:最小割为简单割。
引入一下简单割的概念：割集的每条边都与S或T关联。(请下面阅读时一定分清最小割与简单割，容易混淆)
那么为什么最小割是简单割呢？因为除S和T之外的点间的边的容量是正无穷，最小割的容量不可能为正无穷。所以，得证。
- 证明:网络中的简单割与原图中闭合图存在一一对应的关系。
即有闭合图都是简单割，简单割也必定是一个闭合图。
证明闭合图是简单割：如果闭合图不是简单割(反证法)。
那么说明有一条边是容量为正无穷的边，则说明闭合图中有一条出边的终点不在闭合图中，矛盾。
证明简单割是闭合图：因为简单割不含正无穷的边，所以不含有连向另一个集合(除T)的点，所以其出边的终点都在简单割中，满足闭合图定义。得正。
- 证明最小割所产生的两个集合中，其源点S所在集合(除去S)为最大权闭合图。
首先我们记一个简单割的容量为C,且S所在集合为N，T所在集合为M.
则C=M中所有权值为正的点的权值(即S与M中点相连的边的容量)+N中所有权值为负的点权值的绝对值(即N中点与T中点相连边的容量)。记(C=x1+y1);(很好理解，不理解画一个图或想象一下就明白了)。
我们记N这个闭合图的权值和为W。
则W=N中权值为正的点的权值-N中权值为负的点的权值的绝对值。记(W=x2-y2);
则W+C=x1+y1+x2-y2。
因为明显y1=y2，所以W+C=x1+x2;
x1为M中所有权值为正的点的权值，x2为N中权值为正的点的权值。
所以x1+x2=所有权值为正的点的权值之和(记为TOT).
所以我们得到W+C=TOT.整理一下W=TOT-C.
到这里我们就得到了闭合图的权值与简单割的容量的关系。
因为TOT为定值，所以我们欲使W最大，即C最小，即此时这个简单割为最小割，此时闭合图为其源点S所在集合(除去S)。得正。
至此，我们就将最大权闭合图问题转化为了求最小割的问题。求最小割用最小割容量=最大流，即可将问题转化为求最大流的问题。
然而这是为啥呢
于是就有了最小割定理一系列内容
以下来自百科
- 定理一：如果f是网络中的一个流，CUT(S,T)是任意一个割，那么f的值等于正向割边的流量与负向割边的流量之差。
证明：设X和Y是网络中的两个顶点集合，用f（X,Y）表示从X中的一个顶点指向Y的一个顶点的所有弧（弧尾在X中，弧头在Y中： ）的流量和。只需证明：f=f(S,T)-f(T,S) 即可。
下列结论成立：如果X∩Y= ，那么：f(X,(Y1∪Y2))=f(X,Y1)+f(X,Y2) ，f((X1∪X2),Y)=f(X1,Y)+f(X2,Y) 成立。根据网络流的特点：如果V既不是源点也不是汇点，那么： f({V},S∪T)-f(S∪T,{V})=0；
任何一个点，流入的与流出的量相等。如果V是源，那么：f({V},S∪T)-f(S∪T,{V})=f。对于S中的所有点V都有上述关系式，相加得到：f(S,S∪T)-f(S∪T,S)=f 。
又因为： f(S,S∪T)-f (S∪T,S)= (f(S,S)+f (S,T))-(f(S,S) +f (T,S))= f(S,T)- f(T,S)，所以：f= f(S,T)- f(T,S) 定理得证 [2] 。
- 推论一：如果f是网络中的一个流，CUT(S,T)是一个割，那么f的值不超过割CUT(S,T)的容量。
- 推论二：网络中的最大流不超过任何割的容量。
- 定理二：在网络中，如果f是一个流，CUT (S,T)是一个割，且f的值等于割CUT(S,T)的容量，那么f是一个最大流， CUT(S,T)是一个最小割。
证明：令割CUT（S,T）的容量为C，所以流f的流量也为C。假设另外的任意流f1，流量为c1，根据流量不超过割的容量，则c1<=c,所以f是最大流。 假设另外的任意割CUT（S1,T1），容量为c1，根据流量不超过割的容量，所以有c1>=c,故，CUT（S,T）是最小割 [2] 。
其实我看不大懂但画画图好像是这样知道就行，证明有点绕