网络流最小割

网络流最小割相关

最小割等于最大流，最小割可以用最大流求的，那么重点在于如何建模，将要求的东西转换为最小割。

最小割求方案

随便输出一种方案只要在残量网络上从源点 BFS ，能到的点在 $S$ 集合中，不能到的点在 $T$ 集合中， $\forall (u,v),u\in S ,v\in T$ 且 $u,v$ 满流则该边属于最小割集。

最小割可行边

就是在某个最小割集中出现的边，设边 $(u,v)$ ，其为可行边的充要条件：

该边满流。
残量网络上不存在 $u$ 到 $v$ 的增广路。

若不满流显然可以找到另一条更小的满流的限制流量的边。
若满流但在残余网络中能找到入点到出点的路径，那么需要同时割掉这条边和残余网络中路径上某条边才能实现“割”，而这两条边上的流量和一定等于其他某条或某几条满流的边的流量和，否则可以继续增广，又因为位于残余网络上的那条边一定不满流，所以这种割法不是最小割。

判断一条边是否可行直接 BFS 即可，单次 $O(n)$
如果在同一个图上大量判断，可以用 tarjan 在残量网络上求 $SCC$ （强连通分量），若 $SCC[u]\ne SCC[v]$ 且 $(u,v)$ 满流则说明该边为可行边。（如果存在 $u$ 到 $v$ 的增广路，那条路径会和 $(u,v)$ 反向边构成环， $u,v$ 会在同一强连通分量里）

最小割必须边

就是在任意最小割集中，该边都存在，设边 $(u,v)$ ，其为可行边的充要条件：

该边满流
残量网络上 $s$ 能到 $u$ ， $v$ 能到 $t$

若不满流显然可以找到另一条更小的满流的限制流量的边。
若满流但在残余网络中源点不能到入点或出点不能到汇点，那么在每条单独路径上一定都存在一条满足最小割可行边的边（容量为 0 阻断路径且没有其他路径），割掉这条可行边是等价的。
必须边的另一种理解是扩大容量后能增大最大流的边。

从 $s$ BFS，从 $t$ 反向BFS，标记能到的点，再枚举满流边即可。
如果求过 $SCC$ ，枚举满流边判断 $SCC[u]=SCC[s],SCC[v]=SCC[t]$ 即可（因为有反向边， $u$ 到 $s$ 肯定连通， $t$ 到 $v$ 肯定连通）

最小割任意方案

每次选取一条满流边，判断其是否为可行边（BFS 一下）
若可行则算入方案，并需要删除它的影响，需要退流： $u$ 向 $S$ 退流， $v$ 向 $T$ 退流，倒着跑 Dinic 。并删除 $(u,v)$ 及其反向边，流量都赋零。

求字典序最小最小割 ，见「SDOI2014」LIS

最少割边最小割

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

最大权闭合子图

闭合图：对于一张有向图 $G$ 存在点集 $V$ 满足对于任意点 $u\in V$ 其出边所到点 $v$ 都有 $v\in S$ 。
最大权闭合子图：每个点带上一个权值 $val_u$ （可正可负），点权和最大的闭合子图就是最大权闭合子图。

建图

建立超级源汇 $s,t$ ，对于正权点 $s\to u$ 边权 $val_u$ ，对于负权点 $u\to T$ 边权 $|val_u|$
对于原图上的边，边权全部为 $+\infty$

跑最大流，答案等于 ( 正权点之和 $-$ 最大流 )

证明：

最小割 $=$ 最大流。最小割将图划分成两块，于 $s$ 向连的记 $S$ ，剩下的记 $T$ 。

$S$ 必然是闭合子图，因为原图上的边都是 $+\infty$ 不可能被割，对于一对入点出点必然同属于 $S$ 或 $T$ 。

对于原图贪心地想，考虑所有正点都选中，然后调整图使其为闭合图（删尽量少的正点权，加尽量少的负点权），对应到新图上就是删除尽量少的边得到一个闭合子图，就是最小割呗。

答案含义就是：正权点之和 - (删除最小的正点权和 + 增加的最小的负点权和 )

求方案

考虑割的含义，对于边 $s\to u$ ，割了这条边表示删了 $u$ 这个正点；对于边 $v\to t$ ，割了这条边表示加了 $v$ 这个负点。故求完最小割后， $S$ 中的点就是最大权闭合子图中的点。

直接 BFS

例题：太空飞行计划问题 CODE

处理集合间的矛盾关系

一个简单的模型：
$n$ 个物品，和两个集合 $A,B$ ，每个物品纳入 $A$ 或 $B$ （二选一），放入 $A$ 代价 $a_i$ ，放入 $B$ 代价 $b_i$ ，还有若干个限制，描述为 $u\in A,v\in B$ 则有 $w$ 的代价。

建图

$s\to u$ 边权 $a_u$ ， $u\to t$ 边权 $b_u$
对于限制 $u\in A,v\in B$ 有代价 $w$ ： $v\to u$ 边权 $w$

求最小割即可。
可以理解为，割了 $s\to u$ 的边 $u$ 就属于 $A$ ，割 $u\to t$ 的边， $u$ 就属于 $B$ ，显然不会两条边都割（不然就不是最小割了）。见下图，如果 $u\in A,v\in B$ （即割了边 a,d）此时还需要割 f 才能使 $s,t$ 不连通，故会算上 $w$ 的代价。

上图的建边是一个通用的模型，上图的最小割有四种情况，分别对应 $u,v$ 的属于集合的不同情况：

a,b: $u\in A,v\in A$
c,d: $u\in B,v\in B$
a,d,f: $u\in A,v\in B$
b,c,e: $u\in B,v\in A$

然后具体边权就视题目而定了。有些时候不是求最小代价而是求最大贡献，那就反一下，先把所有贡献算上，减去最小的不取的贡献就行了。

例 [国家集训队]happiness

喜悦值总和最大 $=$ 未收获喜悦值总和最小

对于某个人 $x$ ：

源点向 $x$ 连容量为 ( 他选文科的喜悦值 $+$ 他和四周的人都选文科的喜悦值/2 ) 的边。
$x$ 向汇点连容量为 ( 他选理科的喜悦值 $+$ 他和四周的人都选理科的喜悦值/2 ) 的边。
$x$ 向旁边的所有点连容量为 ( 他们同时选文科 $+$ 理科的喜悦值/2 ) 的边。

手模一遍四种割法，可以证明其是对的。 CODE

最小割转最短路

有时点数过多，网络流会 TLE ，对于平面图（一般处理网格图），可以转化成对偶图求最短路问题，原图需无向

具体做法见 here

例 [ICPC-Beijing 2006]狼抓兔子