【笔记】网络流选讲

（待修订）连通块（最小割）

有 \(k\) 棵 \(n\) 个点的树，点带权 \(a_i\) 可负，求一个权值集合，使得它在 \(k\) 棵树上都是连通块。\(n\leq 50000\)

考虑如果固定根，把 \(k\) 棵树拉出来，则这时，若选择了一个权值，则它在所有树上的父亲都要选。

将权值建点，连向它在每棵树上的父亲。跑最大权闭合子图。

点分治解决。

[CF1082G] Petya and Graph（最小割）

强制保留所有边。对原图所有点和边都建图，对于 \(e=(u, v)\)，连边 \(S\to u, S\to v\) 流量上限是这两个点的点权，\(u\to e, v\to e\) 流量上限 \(+\infty\)，\(e\to T\) 流量上限是 \(e\) 的权值。跑最小割。正确性由连通性意义发现。

[CF1383F] Special Edges（最小割）

改成最小割，先 \(O(2^k)\) 地枚举应该割掉的边集，应该割掉的边权设为 \(0\)，不应该割掉的边权设为 \(+\infty\)（这里只需要看割的意义）。询问也同样枚举。

优化是因为 \(w\leq 25\) 的限制，一开始枚举的时候先钦定所有特殊边都割断，枚举集合时做增流的步骤。

（待修订）[清华集训2017] 无限之环

skipped

[AGC031E] Snuke the Phantom Thief（匹配）

枚举选多少个点，将限制变成对范围外第一个单点的限制，那么最终横坐标第 \(i\) 小、纵坐标第 \(i\) 小的就会有一个区间限制。做一遍 chkmin & chkmax 的工作后，单调性可以忽略，可以用 mcmf 做匹配（注意横坐标纵坐标的限制是分别排序后的，一个点可以是横坐标第 \(i\) 小同时是纵坐标第 \(j\) 小）。

[AGC029F] Construction of a tree（匹配）

首先做二分图匹配，从每个集合里面选出这个集合对应的一个儿子。那么要么匹配不上 \(n-1\) 个点，要么剩下一个点，我们就钦定为根，从根开始 dfs，选出它的所有儿子，递归下去。

如果发现没匹配完，说明有不连通的部分，这部分的点数等于边数，也就寄了。

[Gym102201J] Jealous Teachers（匹配）

首尔科学高中有 \(N\) 名教师和 \(N\) 名学生。每个学生购买了 \(N\) 朵花，因为明天是韩国的教师节。然而，其中一名学生退学了，现在学校只剩下 \(N-1\) 名学生。每位教师应该收到正好 \(N-1\) 朵花。学生只能将花送给教过他们的教师，而你知道哪些学生是从哪些教师那里学习的。永勋是首尔科学高中的学生，他需要你的帮助来组织这个活动。

\(2 \le N \le 100 000\)，\(1 \le M \le 200 000\) 并要求构造方案或无解。

先找一个匹配，将所有匹配的边流满，这样会多出学生到某些老师的 \(n-1\) 流量的反悔边，并有 \(n-1\) 个老师的边会断掉（到源点的流量没有意义），所有学生只剩下一个流量，只有一个老师有 \(n-1\) 流量。

这意味着这一位老师需要将流量送给每一个学生。因为中间的边流量为 \(n-1\)，已经是最大流量了，老师可以随意经过而无限制。那么我们看一下图是否连通就好了。

[ECF2022K] Magic（匹配-独立集）

对于两个相交不包含的区间 \(l_1<l_2<r_1<r_2\)，\(l_2\) 和 \(r_1\) 的答案只能留下一个。可以给这两个端点连边，刚好有左右端点之分，是二分图，获得其最大独立集即可。

可以发现，答案不会比最大独立集大。同时也可以发现最大独立集不会比答案大，因为我们一定能通过拓扑排序获得操作方案：拓扑排序过程中，区间的左端点会逐渐右移（或者逐渐左移），不会出现环。

对于包含的区间：反正不需要求方案，不需要与被包含的区间做任何事情。

[CCPCF2022H] This is not an Abnormal Team!（匹配）

有一张二分图，请将它划分为大小为 \(1\sim 3\) 的连通块，满足

• 大小为 \(1\) 的连通块尽量少。
• 在此基础上，大小为 \(3\) 的连通块尽量少。

\(n\leq 10^5, m\leq 2\times 10^5\)。

跑一个最大匹配，那么一个连通块内未匹配的点一定全在左侧或右侧（否则存在增广路）。以左侧为例，将所有匹配上的边 \((u\to v)\) 连边 \(u\to T\) 边权为 \(1\)，未匹配的左侧点 \(u\) 连边 \(S\to u\) 边权为 \(1\)。原来的反悔边保留，跑最大流。可以发现一个流会伴随着若干匹配的改变和一个大小为 \(3\) 的连通块的出现，总之是合情合理的。

注意这题不是求最小边覆盖！

（待修订）[HNOI2013] 切糕（最小割-切糕）

（最会的一集，回头写一下你的过程）

切糕模型：有若干变量 \(x_1, x_2, \cdots, x_n\)，有函数 \(f(i, v)\) 为当 \(x_i=v\) 时的代价。另外可以对 \(x_i, x_j\) 做限制，可以当 \(x_i\geq u\) 且 \(x_j\leq v\) 时有一个代价（左下限制），也可以 \(x_i\leq u\) 且 \(x_j\geq v\) 时有一个代价（右上限制）。可以求最小总代价。

切糕模型甚至可以做最长反链。

[CF1630F] Making It Bipartite（最小割-切糕）

题目条件即为不能出现 \(a|b\land b|c\)。如果只是 \(a|b\)，那么是最长反链。

有一个与切糕类似的做法，我们将 \(a|b\) 的关系拆成四个点三条边 \(a_1\to a_2\to b_1\to b_2\)，并希望给每个点标一个 \(0\sim 2\) 的标号，满足 \(a_2=a_1\)（删去）或 \(a_2=a_1+1\)（保留），\(b_1=a_2\)。为了连更多的边我们将限制改为：

• \(a_2\leq b_1\) 是钦定的。
• \(a_1+1\leq a_2\) 则支付 \(0\) 的代价，否则支付 \(1\) 的代价。

套用切糕模型，求出最小割，最小割即为删去点的数量。

[CF786E] ALT（最小割）

这题是诈骗的，直接变成居民向路径上的所有守卫连边，要么选居民，要么选一堆守卫。任意数据结构优化建图。

[Gym103855I] Marbles（上下界）

两个袋子 \(u, v\) 合并，将它们以 \([0, \infty)\) 边连向新袋子即可。观察到袋子 \(u\) 的红色珠子数量在 \([l, r]\) 之间，我们向一个新的袋子连一条流量 \([l, r]\) 的边，表示我现在限制它一下。丢掉一个珠子，我们从它所在的袋子向它连一条 \([0, 1]\) 的边，表示我丢掉它，流量送回去。最后统一将所有珠子丢掉。

为什么要这样做呢，因为这样就发现从每个珠子出发有一个回到它自己的圈（环），而且流量因为最后一条边限制是 \([0, 1]\)。如果确认它是红色，那么将这个圈流一个流量，否则不流。这样我们就只需要求上下界可行流了。