4.1.1 基本方法

大家肯定都会 \(\text{Dinic}\)，也知道啥是最大流最小割定理，所以我们直接快进到建图。另外写 \(\text{ISAP}\) 没有 \(\text{Dinic}\) 在单位图和二分单位图上的复杂度优化，所以最好别写 \(\text{ISAP}\)。

下面统一把 \(S\) 侧称为左边，\(T\) 侧称为右边。

最大流的建图¶

给出一张二分图，选出尽可能多的边，使得任意两条边没有公共端点

显然，在 \(S\) 向所有左部点连权值为 \(1\) 的边，对于每个边 \((u,v)\)，由左部点 \(u\) 向右部点 \(v\) 连权值为 \(1\) 的边，所有右部点向 \(T\) 连一条权值为 \(1\) 的边。

二分单位图，复杂度 \(\mathcal O(m\sqrt n)\)。

给出一张有向图，你需要选择出尽可能少的点不交的简单路径，使得每个 DAG 上的点都在某条路径上。

所有点视作独立的一条路径，然后考虑把若干个点合并成一条路径，具体地，每个点可以和它出边连到的点合并。

对每个点建两个点 \(u\) 和 \(u'\)，对于原图里面的每条边 \((u,v)\)，连 \((u,v')\)。

这个时候就是二分图最大匹配了。

同上一题，但是没有点不交的限制。

先求出每个点 \(x\) 能到达所有点 \(y\)，\(x\) 向这些点分别连一条边，直接套用上一题的做法。

重复经过的点就相当于被跳过了，正确性证明我也不知道。

显然我们有一些更加对的做法，考虑（后面的）上下界网络流。

对每个点 \(u\)，所以 \(S\) 向 \(u\) 连一条流量为 \(1\) 的边。

每个 \(u\) 初始都是一条路径，但是一个点可以被多个点匹配，所以 \(u\) 向 \(u'\) 连一条下界为 \(1\)，上界为 \(+\infty\) 的边。

对于原图中的每条边 \((u,v)\)，连流量为 \(1\) 的 \((u',v)\)。求有源汇上下界最大流即可。

复杂度 \(\mathcal O(m(n+m))\)。

取出最少的点，使得每条边至少有一个端点被选择

等于二分图最大匹配。

考虑和最大流同样一个图的最小割，考虑右边所有被选的点表示被覆盖了，

有一张有向图，点权有正有负，如果一个点选了，所有从它出发可以到达的点都必须被选，求最大的权值。

在原图的基础上，\(S\) 向所有正权点连一条容量为点权的边，所有负权点向 \(T\) 连一条容量为点权的相反数的边。

这个时候跑最小割，左边割掉的边表示不选对应点，右边割掉的边表示选对应点。

因为 \(S\) 和 \(T\) 不连通，所以从左边的任何一个保留的点出发，只能到达被选择了的点。这确实是一个闭合子图。

答案显然是，所有正权之和减去最小割。