P4542:「ZJOI2011」营救皮卡丘 – 题解

主要思路

妈卖批，完全想偏了。刚开始思考的时候以为是要搞一颗有根的、根到叶子路径都满足递增。

后面发现其实这个图也有可能是个 DAG，而且树的话可能会因为 K 的限制没法搞。所以，我们就可以直接路径覆盖然后求最小费用即可。

一眼可以看出一个 \(\Theta(n^3)\) 的 DP。其实用双带权二分就可以用 \(\Theta(n \log^2 n)\) 的时间搞了，但是我没写这个写法。

考虑一下被选择时的贡献。\(p_a, p_b\) 是单元贡献，考虑同时被选的贡献 \(1 – (1 – p_a)(1 – p_b) = p_a + p_b – p_a p_b\)。所以我们可以考虑最大费用最大流，来算这个式子。

需要注意的是，我们需要保证每一次代价都是正的，因为我们其实并不需要最大流，而只是相对的最大费用。

忘了写题解，但总觉得要写点啥，所以就有了这篇题集。

这道题还是很妙的，我只想到了最大费用最大流之后就想不动了。

我们在这里介绍边数为\(O(n)\)级别的解法。考虑把所有的端点离散化为\(2n\)个连续的点，然后相邻端点\(i, i+1\)相互连接流量无限、费用为零的边。考虑区间左右端点，左端点连到右端点，流量为\(1\)，费用为区间长度。最后源点连左端点，汇点连到右端点。

这样就可以强制满流，且费用最大。

这道题真的是送分题（快要想出来直接暴力枚举+并查集的时候去看了题解，最后发现就是这么 sb）。

考虑枚举频段区间\([L, R]\)（将边进行排序，确定下界之后再枚举上界），这个地方是\(O(m^2)\)的。每次枚举下界的时候都要初始化并查集，然后合并两个集合的时候按照大小来修改答案就行了。

在有向图中，有唯一的源地（入度为 0）和汇点（出度为 0），每一条边都有非负的容量，且整张图都会保证平衡状态。这样的图叫做网络流图。

每秒钟每条管道流动的液体最多。常用的算法是 Dinic。先做一次 BFS 划分层次，再用 DFS 来进行流动。Dinic 算法就是在网络图上对残存网络进行利用求得最大流。

其中值得一提的是，Dinic 算法中有一个优化方式可以快速求最大流——当前弧优化。当前弧优化可以在每次找残余网络之前记录遍历到的 head 指针，避免不必要的遍历。