网络流建模之 DAG 最小路径覆盖

· · 个人记录

路径不相交

模板题：P2764 最小路径覆盖问题

首先显然可以用 n 条路径覆盖，每条路径只覆盖一个点。

考虑每次合并两条路径，将起点为 y 的路径接到终点为 x 的路径后边，这样路径总数减一。

将每个点拆成两个点 a_i,b_i，连边 (S,a_i) (b_i,T)，以下默认所有边流量为 1。

因为 (S,a_i) (b_i,T) 的流量为 1，所以每个点只会被接到一个点后边，也只会把一个点接到后边。

若存在边 (x,y)，则连边 (a_x,b_y)，表示将起点为 y 的路径接到终点为 x 的路径后边。

因为建出的是二分图，且边权为 $1$，所以时间复杂度 $O(m\sqrt n)$。 不是 DAG 怎么做？ 如果允许一条路径经过一个点多次，先缩点再用之前的做法。 否则可以直接用之前的做法。 习题： [P2765 魔术球问题](https://www.luogu.com.cn/problem/P2765) [P2172 [国家集训队]部落战争](https://www.luogu.com.cn/problem/P2172) [P2469 [SDOI2010]星际竞速](https://www.luogu.com.cn/problem/P2469) ## 路径可相交 做法 1 先对原图求传递闭包。传递闭包求法见 [bitset 应用总结](https://www.luogu.com.cn/blog/221955/bitset-ying-yong-zong-jie)。 新建一张图，若原图上 $x$ 能到达 $y$，且 $x\neq y$，则新图上连边 $(x,y)$。 对新图跑路径不相交的做法即可。 正确性是显然的。对于一个路径可相交的方案，从中每个点任取一次，其他的全部删掉，就转换成了新图上路径不相交的方案。新图上路径不相交的方案，对于边 $(x,y)$ 加入原图 $x$ 到 $y$ 路径上的所有点，就转换成了原图上路径可相交的方案。 例题：[P4298 [CTSC2008]祭祀](https://www.luogu.com.cn/problem/P4298) 根据 Dilworth 定理有最长反链等于最小链覆盖，于是第一问的答案就是路径可相交的最小路径覆盖。对于第二问，求出建出的二分图的最大独立集，也就是最小点覆盖的补集，做法见[二分图总结](https://www.luogu.com.cn/blog/221955/er-fen-tu-xiang-guan#)，保留 $a_x,b_x$ 都出现在最大独立集中的点，即为所求。对于第三问，相当于枚举每个点 $x$，删掉 $x$ 以及 $x$ 能到达的所有点以及能到达 $x$ 的所有点，判断剩余部分的最小路径覆盖是否等于原图 $-1$。 习题：[P4589 [TJOI2018]智力竞赛](https://www.luogu.com.cn/problem/P4589) ## 路径可相交 做法 2 [#217. 【UNR #1】奇怪的线段树](https://uoj.ac/problem/217) 此题边数 $O(n)$，但传递闭包后边数变成 $O(n^2)$，二分图匹配复杂度是 $O(n^{2.5})$。 考虑用上下界网络流。连边 $(S,a_i),(b_i,T),(a_i,b_i)$，对于图中的边 $(i,j)$ 连 $(b_i,a_j)$。$(a_i,b_i)$ 下界为 $1$，其余边下界为 $0$，所有边上界为 $+\infty$，求有源汇上下界最小流即可。因为流量 $O(n)$ 只会进行 $O(n)$ 次 bfs，所以复杂度 $O(n^2)$。 还有一种更简便的建图，连边 $(S,a_i),(b_i,T)$ 流量为 $1$，连边 $(b_i,a_i),(a_i,b_j)$ 流量为 $+\infty$，$n$ 减去最大流即为答案。原因是对于一条 $S\to a_i\to\cdots\to b_j\to T$ 的流，相当于将原图上满足 $i$ 能到 $j$ 的点对 $(i,j)$ 匹配，于是就相当于传递闭包上二分图匹配。