最小割

源点 \(s\)，汇点 \(t\)。

记对残量网络跑 \(\text{tarjan}\) 得到的第 \(i\) 个点所在 \(\text{SCC}\) 编号为 \(scc_i\)

最小割方案

我们可以通过从源点 \(s\) 开始 \(\text{DFS}\)，每次走残量大于 \(0\) 的边，找到所有 \(S\) 点集内的点。

最小割可行边

条件 1：满流（此时残量网络上有边 \(v\to u\)）。

条件 2：不存在 \(u\to v\) 的路径，即 \(scc_u\neq scc_v\)。

运用最大流最小割定理，可以很容易推出条件 1。

对于条件 2，如果 \(u,v\) 在同一个 \(\text{SCC}\) 里，那一定可以通过流量调整（匀一点流量）使得 \((u,v)\) 不满流，此时就不满足条件了。

最小割必经边

条件 1：满流（同样意味 \(v\to u\)）。

条件 2：\(scc_u=scc_s,scc_v=scc_t\)。

如果一条边是必须的，那么增加这条边的容量一定会改变最大流。

残量网络的 \(\text{SCC}\) 缩点后是一个 \(\text{DAG}\)，方向是从 \(T\) 向 \(S\)。

当且仅当 \((u,v)\) 在 \(scc_s\) 和 \(scc_t\) 之间时，增加 \((u,v)\) 的流量才能增大最大流。

最小割最小边数方案

跑完一次最小割后，令所有满流边容量为 \(1\)，非满流边容量为 \(+\infin\)，再做一次最小割，此时的任意最小割方案割边都最少。

最小割任意方案和字典序最小方案

依次枚举每条边。每次选取一条满流边 \((u,v)\)，用 \(BFS\) 判断它是否是可行边。如果是就加入最小割。由可行边判定条件，不能存在从 \(u\to v\) 的增广路径。因此要退回一些边的流量，让它们不会被选进去。具体方法是从 \(u\) 向 \(s\)，\(v\) 向 \(t\) 跑 \(\text{Dinic}\) 退流。

如果让字典序最小,就按编号从小到大枚举即可。题目要求的特定顺序也类似。