图论 2
Published:
网络最大流
TODO:
Dinic 的时间复杂度
Dinic 算法的时间复杂度为 $O(n^2 m)$。但是实际基本上跑不满。
根据知乎问题 如何使最大流的 Dinic 算法达到理论上的最坏时间复杂度？，要卡满 Dinic 的构造也很诡异，而且似乎常数还是很小。（存疑）
根据 OI-Wiki 的说明，Dinic 算法在单位容量网络的特殊情形有可以保证的优秀复杂度：
- 单位容量网络上，Dinic 的复杂度是 $O(\min(m \sqrt m, n^{\frac 2 3} m))$。
- 单位容量网络上，除了源汇点以外每个节点都满足要么入度为 $1$ 要么出度为 $1$，Dinic 的时间复杂度为 $O(\sqrt n m)$。
最小费用最大流
TODO:
网络流的经典模型
点流量限制
我们可以通过拆点的方式限制一个点处的流量。具体来说，我们希望把一个点 $u$ 限流为 $c$，我们把 $u$ 拆成 $in_u$ 和 $out_u$，入边都连到 $in_u$，出边连到 $out_u$，$in_u$ 连一条容量为 $c$ 的边到 $out_u$。
多源多汇
添加超级源和超级汇即可。
最小割——最大流最小割定理
最大流最小割定理：最小割等于最大流。
二分图最大匹配
我们把左图的二分图建成一张右图，每条边的容量为 $1$。通过给左右的边加了 $1$ 的限制，使得每个点都只能存在于一条路径中。
时间复杂度 $O(\sqrt n m)$。
二分图最小点覆盖——Kőnig 定理
最小点覆盖：选择最少的顶点，满足每条边至少有一个端点被选。
Kőnig 定理：二分图最小点覆盖等于最大匹配。
证明
可以把二分图点覆盖规约为最小割问题。
依旧使用上面那节的图。对于一个割，考虑原图的一条边 $u \leftrightarrow v$，这个割中要么有 $S \to u$，要么有 $v \to T$，两者至少割掉一个。可以把“割掉一个点 $u$ 连着的边”，看成“在点覆盖中选择了点 $u$”。
此时原图的每一个点覆盖都和新图的割一一对应。因此我们找到最小割即可。
根据前一节的结论，新图的最大流等于原图的最大匹配。根据最大流最小割定理，最大流等于最小割。一路等过去就得到了最小点覆盖等于最大匹配。
二分图最大独立集
最大独立集：在一张无向图中选择最多的顶点，满足两两之间互不相邻。
任意图上，独立集和点覆盖形成双射（补集关系），最大独立集等于总点数减掉最小点覆盖。
证明：任意图上，对于一个点覆盖 $C$，任意一条边 $e$ 的两个端点至少有一个出现在 $C$ 中，即没有边的两个端点同时出现在 $C$ 的补集中，也就是说 $C$ 的补集是独立集。
二分图最大匹配的必须边与可行边
团：完全子图。
给定一张图 $G$，保证 $G$ 的补图是二分图。现在让你在 $G$ 加一条边，使得 $G$ 的最大团大小至少 $+1$。求出所有方案。
$n \le 10^4$，$m \le 1.5 \times 10^5$，无重边无自环。
原图的团就是补图的独立集。补图是二分图，最大独立集等于 $n$ 减最大匹配。因此我们要找一条能让补图的最大匹配至少 $-1$ 的边，即最大匹配的必须边。
结论：
先 Dinic 求出一个最大流，
- $u \to v$ 是必须边的充要条件：$u \to v$ 流量为 $1$，且 在残量网络上属于不同的强连通分量。
- $u \to v$ 是可行边的充要条件：$u \to v$ 流量为 $1$，或 在残量网络上属于相同的强连通分量。
考虑 TODO:
DAG 最小不相交链覆盖
一般图上的最小不相交链覆盖似乎不可做。但是 DAG 的最小链覆盖可以归约到二分图匹配问题。
考虑用尽量多的边把点连成连通块的思路，最终的连通块数量即为答案。把 $S$ 连到每个点，把每个点连到 $T$；每条边可以选或者不选（选的越多越好）容量为 $1$，每个点的流量最多是 $1$（用前面的拆点技巧实现）。跑网络最大流即可。
其实拆点之后不看源汇点我们就得到了一个二分图（本质是归约到二分图最大匹配），因此这里 Dinic 的时间复杂度是 $O(\sqrt n m)$ 的。
DAG 最小可相交链覆盖
建传递闭包，问题转化为 DAG 最小不相交链覆盖。
时间复杂度 $O(\frac {n m} w + n^{\frac 5 2})$，后面那个 $\frac 5 2$ 我不确定能不能跑满，但是主要的瓶颈在传递闭包。
P.S. “最小路径覆盖”一般指“最小不相交链覆盖”，“最小链覆盖”一般指“最小可相交链覆盖”。
Dilworth 定理
DAG 可以表示偏序关系。根据 Dilworth 定理，DAG 的最小可相交链覆盖等于它的最长反链。
也就是说，上面的那个做法其实给出了任意偏序集最长反链（也叫宽度，partial order width）的做法。来自 OI-Wiki，💡P4298 [CTSC2008] 祭祀。
P1020 [NOIP 1999 提高组] 导弹拦截 是 Dilworth 定理的一个应用，虽然这题因为 LIS 这个东西性质比较好，用不着网络流。
最大权闭合子图
给定一张有向图 $G$，点有点权（可以为负）。
闭合子图的定义：是原图的子图，对于任意子图内的节点，它连向的还是子图内的点。
求 $G$ 的点权和最大的闭合子图。输出权值。
对于一个正点权 $k$ 的点 $u$，连边 $S \to u$ 权值为 $k$；对于一个负点权 $-k$ 的点 $u$，连边 $u \to T$ 权值为 $k$（其点权的绝对值）。原图的边权值设为 $\infty$。
对着这张图跑最小割 $c$，答案为所有正点权之和（即 $S$ 的所有出边）减掉 $c$。
特别地，$0$ 点权的点什么都不用做，因为边权为 $0$ 的边不影响最小割。
证明：
对于正权点 $u$，若 $S \to u$ 被割掉，则代表 $u$ 不属于选择的闭合子图，反之亦然；对于负权点 $v$，若 $v \to T$ 被割掉，则代表 $v$ 属于选择的闭合子图，反之亦然。
一种等价的说法是，若点 $u$ 和 $S$ 在割的同侧，则 $u$ 在选择的闭合子图中。事实上，任何一个有限容量的割都对应一个原图的闭合子图。
最小割 = 不选的正权之和 + 选择的负权绝对值之和 = 不选的正权之和 - 选择的负权之和 = 所有正权和 - 选择的所有点权之和。所有正权的和是定制，而最小割又是最小的割，因此此时选择的所有点权之和就是最大的。
上下界网络流
| [P5192 Shoot the Bullet | 东方文花帖 | 【模板】有源汇上下界最大流](https://www.luogu.com.cn/problem/P5192) |
每条边不仅有流量上界（容量），还多了一个容量的下界。求：
- 无源汇上下界可行流：是否存在一种满足每个点流量守恒的流量网络；
- 有源汇上下界可行流：是否存在一种满足除了 $S,T$ 以外每个点流量守恒的流量网络；
- 有源汇上下界最大流：$S$ 到 $T$ 的最大流；
- 有源汇上下界最小流：$S$ 到 $T$ 的最小流。
- 有源汇上下界费用可行流：$S$ 到 $T$ 的最小费用可行流。
无源汇上下界可行流
添加超级源 $S’$ 和 $T’$。对于每一条边 $u \to v$ 流量范围 $[l,r]$，在新图上这样处理：
- $S’ \to v$ 容量为 $l$
- $u \to T’$ 容量为 $l$
- $u \to v$ 容量为 $r-l$
此时求出 $S’ \rightsquigarrow T’$ 的最大流，若 $S’$ 的所有出边满流，则原图存在可行流。
有源汇上下界可行流
连边 $T \to S$ 流量范围 $[0, \infty)$，归约为无源汇上下界可行流。
有源汇上下界最大流/最小流/费用可行流
这段的证明略去，只讲做法。
先跑一次有源汇上下界可行流，然后撤去 $S’,T’$ 两个点和 $T \to S$ 的 $[0, \infty)$ 边。
- 最大流：在此时的残量网络上跑一次 $S \rightsquigarrow T$ 的最大流，将可行流流量和最大流流量相加。
- 最小流：在此时的残量网络上跑一次 $T \rightsquigarrow S$ 的最大流，将可行流流量和最大流流量相减。
- 费用可行流：把最大流算法改为费用流算法。TODO: 具体细节不知道，网上都是这么说的。Pecco
- 附加边的费用设为 $0$。
- 💡P4043 [AHOI2014/JSOI2014] 支线剧情
TODO: 费用流这段考虑的不够完善，无源汇、有源汇、有负环
动态建图
TODO:
网络流 例题
非线性费用
边的容量为 $c$，边有一个系数 $a$，表示该边流量为 $x$ 时费用为 $a x^2$。$c$ 比较小。
怎么处理这样的条件？
拆边：连 $c$ 条容量为 $1$ 的边，费用依次为 $a, 3a, 5a, \cdots$。最小费用最大流会贪心地先走费用小的边，保证了正确性。
P3973 [TJOI2015] 线性代数
给定 $n \times n$ 的数组 $b$ 和长为 $n$ 的数组 $c$。
你要构造一个长为 $n$ 的 $01$ 数组 $a$，最大化以下值：
\[\sum\limits_{i=1}^n \sum\limits_{j=1}^n a_i a_j b_{i,j} - \sum\limits_{i=1}^n a_i c_i\]输出这个最大值。
$n \le 500$。
若 $b_{i,j}$ 被选择，则 $a_i,a_j$ 只能均为 $1$；若 $a_k$ 为 $1$，则 $c_k$ 只能被选择。这是一个最大权闭合子图问题。
P4843 清理雪道
给定一张 DAG，定义一次操作为：从任意点出发，不断前进直到到达出度为 $0$ 的点，标记沿途经过的边。求标记所有边的最小操作次数。
省流：DAG 的边的最小可相交链覆盖。
$n \le 100$。
把边也建成点，跑 DAG 最小可相交链覆盖。但是 Tarjan 算传递闭包时间复杂度是 $O(\frac {m^2} w)$ 即 $O(\frac {n^4} w)$，可能有点难过。
换个思路：对每个点 $u$ 连边 $S \to u$（容量不限）；对每个出度为 $0$ 的点 $u$ 连边 $u \to T$（容量不限）；对于原图的每个边 $u \to v$ 设定下界 $1$。跑一个有源汇上下界最小流。
P4134 [BJOI2012] 连连看
TODO:
P2053 [SCOI2007] 修车 / P2050 [NOI2012] 美食节
有 $n$ 种车来到了汽车维修中心，第 $i$ 种车有 $p_i$ 辆。有 $m$ 位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的，第 $j$ 个技术人员修第 $i$ 辆车所需的时间是 $T_{i,j}$。现在需要安排这 $m$ 位技术人员所维修的车及顺序，使得每辆车平均等待的时间最小。
说明：每辆车的等待时间是指从车来到维修中心到维修完毕所用的时间。
- Easy Version：$n \le 60$，$m \le 9$，$p_i = 1$，$T_{i,j} \le 10^3$。
- Hard Version：$n \le 40$，$m \le 100$，$\sum p_i \le 800$，$T_{i,j} \le 10^3$。
TODO:
P4542 [ZJOI2011] 营救皮卡丘
给出一张 $n+1$ 个点，$m$ 条边的无向连通图，每条边有非负权值。
有 $k$ 个人从 $0$ 号点出发，可以分开。
对于每个点 $i$，必须在已经经过 $i-1$ 号点后才能通行。
求到达 $n$ 号点的最小代价。
保证有解。$n \le 150$，$m \le 2 \times 10^4$，$k \le 10$，边权值域 $10^4$。
TODO:
P7730 [JDWOI-1] 蜀道难
TODO:
P4251 [SCOI2015] 小凸玩矩阵
TODO:
[ARC080F] Prime Flip
有无限个硬币，其中第 $x_1, x_2, \cdots, x_n$ 个硬币反面朝上，其余正面朝上。
每次可以选一个奇质数 $p$ 和一个位置 $x$，把 $[x,x+p)$ 区间的所有硬币翻转。
求使得所有硬币正面朝上的最小操作数。
$n \le 100$。$x$ 的值域为 $10^7$。
区间翻转可以用差分。每次操作相当于在 $x$ 和 $x+p$ 两处打上标记。
考虑一对位置 $(l,r)$，我们现在希望通过若干步操作叠加，达到同时反转 $l$ 和 $r$ 的效果。
- 若 $r - l$ 是奇质数，则花费 $1$ 次操作。
- 若 $r - l$ 是偶数，则花费 $2$ 次操作。说明：
- 若 $r - l \ge 6$，由 Goldbach 猜想可知它必然能被拆成两个奇质数之和。
- 若 $r - l = 2$，拆成 $5 - 3$。
- 若 $r - l = 4$，拆成 $7 - 4$。
- 若 $r - l$ 是奇数但不是质数，则花费 $3$ 次操作。
- 对于 $r - l = 1$ 的情况，拆成 $7 - 3 - 3$。
- 对于其余的情况，可以先反转 $l$ 和 $r - 3$（距离为偶数，花费 $2$），再反转 $r-3$ 和 $r$。
显然每种操作我们只会对有标记的两个位置进行。
花费为 $1$ 的怎么找？显然 $l,r$ 的奇偶性不同，所以形成了一个二分图，花费为 $1$ 的操作形成了这个二分图的一个匹配。
对于剩下的点，考虑花费为 $2$ 的操作，那么就是左部点内部配对和右部点内部配对。最终要么刚好全配完，要么左右各剩一个（因为总点数是偶数，$n$ 个位置有 $2n$ 个标记，标记抵消不影响总标记数量奇偶性）。如果是左右各剩一个，则使用花费为 $3$ 的。
我们猜测：贪心地先使用花费为 $1$ 的，再使用花费为 $2$ 的，最后使用花费为 $3$ 的，就能得到最优解。实际上正确性非常好证：令左部点和右部点的个数为 $L,R$，$1$ 操作的个数为 $x$，则总花费 $f(x) = x + 2 \left\lfloor \frac {L - x} 2 \right\rfloor + 2 \left\lfloor \frac {R - x} 2 \right\rfloor + 3 ((L - x) \bmod 2)$，能证明 $f(x)$ 单调递减，选取 $x$ 最大的值即可。
也就是说我们需要一个二分图的最大匹配。做完了。
References
OI-Note Chapter2.5 网络流与二分图 - command_block