最大流最小割

首先要知道什么是割(cut)。割是把图的节点划分成两个集合S和T，那么有一些边的端点是分别处于S和T中的。所谓最小割就是

使这些边的边权之和最少的划分。

而对与网络流的最小割也是一样的，例子如下

网络流的相关知识

则分割的代价为12-4+11=19。要注意的是网络流的割的边权为这条边可以提供的流量。

定理：最大流等于最小割。

如果要求属于S集合的点的话，就只需跑完网络流之后再一次bfs，访问过的点就是属于S集合的点。

若是求图的最小割还有一种随机化的Karger算法，比跑网络流快多了，复杂度为mlogm。我还没学，这里给一篇好的博客https://www.cnblogs.com/demoZ/p/4295440.html

最小路径覆盖

给定一个有向无环图，用最少的路径数量去保证所有点都被覆盖住。

网络流的相关知识

做法把点分成前驱结点和后继节点，连边。

网络流的相关知识

最小路径覆盖的结果等于N-最大二分匹配。

为什么呢？首先我们要知道一条路径的起点入度为0，换句话说，一条路径的起点，它在B部一点是没有被匹配上的。

经过最大匹配算法后，B部剩下没有被匹配的点一定是最少的，也就对应了最小需要的路径数。

有一个有向图，每一个点都有一个权值（可以为正或负或0），选择一个权值和最大的子图，

使得每个点的后继都在子图里面，这个子图就叫最大权闭合子图。

网络流的相关知识

能选的子图有Ø,{4},{3,4},{2,4},{1,2,3,4},它们的权值分别为0,-1,5,-6,4.
所以最大权闭合子图为{3,4}，权值为5。

这个问题可以转化为最小割问题，用网络流解决。

从源点s向每个正权点连一条容量为权值的边，每个负权点向汇点t连一条容量为权值的绝对值的边，

有向图原来的边容量全部为无限大。

网络流的相关知识

求它的最小割，割掉后，与源点s连通的点构成最大权闭合子图，权值为（正权值之和-最小割）。