Network Flow

渐渐开始理解网络流的题型了，是一种可以自由分配，求最优分配方案的题。
由于最短路算法是最小费用最大流算法的子算法，所以有些最短路的题可能要用到最小费用最大流。
在最小路经覆盖中，原图的邻接矩阵和二分图匹配的邻接矩阵为同一矩阵。
当网络流的节点数过多且可分类的时候，应思考是否可以分多次进行最大流来求解。

最小割

网络流的最小割问题，看到分配成两部分的题，就要想到网络流最小割。最小割就是将原图划分为两部分，一部分包含源，一部分包含汇。割值是一部分指向另一部分的边的初始容量的总和，不加上另一部分指向本部分的边的容量。而对于最小割来说，最大流流量就是最小割的容量。因为在最大流的过程中总有一些边成为流量继续增加的瓶颈，而这些边一定是流满的，只要将这些边割开就必定可以阻断所有流。最大流后分析原图如何划分的方法，就是将最大流后残余网络中s可以走到的点划为s集合，其余点划为t集合，注意，不是可以走到t的点，因为有可能有一条线上的多条边都流满的情况，这种情况下有些点就无法走到t，而且s也走不到它。最大权闭合子图

对于网络流最小割的建图，通常并不是直接想到最小割，而是先建立一个结点带权，边不带权的图，并对该图求最大权闭合子图。闭合子图：从图中选出若干个点，及这些点相邻的边，若所有边的端点都是被选出的点，则该子图为闭合子图。为求最大权闭合子图而把问题转化为网络流的最小割。转化的具体方法是，把所有结点到结点的边都设置为容量为正无穷的边，并从源引边到权值为正的结点，边的容量为点的权值。从权值为负的点引边到汇，边的容量为结点权值的相反数。

网络流的最小割对应着最大权闭合子图，这个闭合子图是所有割后源点能到达的所有点。而这个闭合子图的权就等于原图中所有正权点的权和减去最小割。一个正权点的边被割，则其能到达的负权点不必因为它被割，若正权点不被割，则其能到达的负权点必须被割，否则图连通。没被割的正权点和被割的负权点必然组成一个闭合子图。所以每种割法都对应着一个闭合子图。被割掉的边对应的点有两种，一种是没有被选中的正权点，另一种是被选中了的负权点。我们用正权和减去最小割得到的是，被选中的正权点减去被选中的负权点的权值（绝对值）。减数越小，结果越大。为保证闭合子图权值最大，得是割值最小。

最大权独立集

网络流最小割还对应着二分图最大权独立集。即每个点有个权值（正值），选中一些点，使得任意两点不相邻，且权值最大。最大权独立集等于点权和减去最小权覆盖集。最小权覆盖集等于最小割。网络流建图方法：源与二分图第一集合中的点连接，二分图第二集合中的点与汇连接，流量均为权值。把二分图之间的边在网络流图中添加为流量正无穷的边。若一个与源连接的点未被割，则其相邻的与汇连接的点必定被割。这几个二分图中的边就至少有一个点被割。所以每种割对应一个点集覆盖。最小割对应最小点集覆盖。

网络流的化简

网络流有时需要对图进行化简

化简规则：

规律 1. 如果几个节点的流量的来源完全相同，且流量为+∞，则可以把它们合并成一个。
规律 2. 如果几个节点的流量的去向完全相同，且流量为+∞，则可以把它们合并成一个。
规律 3. 如果从点 u 到点 v 有一条容量为 +∞ 的边，并且 u 是 v 的唯一流量来源，或者 v 是 u 的唯一流量去向，则可以把 u 和 v 合并成一个节点。

最小点集覆盖

最小点集覆盖==最大匹配。在这里解释一下原因，首先，最小点集覆盖一定>=最大匹配，因为假设最大匹配为n，那么我们就得到了n条互不相邻的边，光覆盖这些边就要用到n个点。现在我们来思考为什么最小点击覆盖一定<=最大匹配。任何一种n个点的最小点集覆盖，一定可以转化成一个n的最大匹配。因为最小点集覆盖中的每个点都能找到至少一条只有一个端点在点集中的边（如果找不到则说明该点所有的边的另外一个端点都被覆盖，所以该点则没必要被覆盖，和它在最小点集覆盖中相矛盾），只要每个端点都选择一个这样的边，就必然能转化为一个匹配数与点集覆盖的点数相等的匹配方案。多个覆盖点都只能选则同一个点组成匹配的情况是不会出现的。因为如果出现这种情况的话，那么这几个点一定不是最小点集覆盖。因为这几个点（设为点集合S）既然只有一个点A可以组成匹配，说明这些S中的点除去与点A的边之外的其他边的另一端都是覆盖点，即S中点的其他边都已被其他点覆盖到，S里点被选为覆盖集是要覆盖S与A连接的那条边，所以最小点集覆盖应该选那个点A即可覆盖这些边，而不选S中的点。所以最大匹配至少为最小点集覆盖数，即最小点集覆盖一定<=最大匹配。综上，二者相等。

最大独立集

求二分图的最大独立集＝ x + y – maxmatch;

原因如下，maxmatch为最大匹配，最大匹配=最小点集覆盖。最小点集覆盖要求每个边至少要有一个端点被选中，最少选几个。而用总点集取最小点集覆盖的补集的意义就是，每条边至多有一个点被选中，最多选几个。这恰好就是最大独立集的要求/

最小路径覆盖

最小路径覆盖，给定一个有向图，在这个图上的某些点上放伞兵，可以使伞兵可以走到图上所有的点。且每个点只被一个伞兵走一次。问至少放多少伞兵。

我们可以把问题转化为，在图上的边中选出一些边，使得每个点的入度与出度都不超过1。

我们开始在图上的每个点都放上伞兵，然后没选出一条边，就意味着有一个伞兵可以被取消掉了。也就是说需要的最少伞兵数=点总数－能选出的最大边数。

我们只要求最大边数即可。用二分图匹配，把每个点拆成两个点，分别加入二分图的两个点集，原图中一条由a到b的边在二分图中是一条由第一个点集中的第a个点到第二个点集中的第b个点。也就是第一个点集的点与出边有关，第二个与入边有关。匹配时也就保证了每个点的如度与出度都不超过1。求最大匹配即为能选出的最大边数。

最小费用最大流

最小费用最大流的意思是：最小费用的最大流，即在众多情况的最大流中挑选一个费用最小的。其计算流程大致是：每次找到一条根据费用来看的最短路，然后对这条最短路进行增加流量，直到所有路径流量都不能增加为止。

网络流，对流过每个点的流量有限制，这样就需要拆点，把每个结点拆成两个，一个入点，一个出点，并从入点到出点连接一条边流量为点的的流向限制。至于原来的点与点之间的边的流量就是正无穷。