Public Judge Round 5

· · 个人记录

这次 PR 打得很自闭，如果 NOI 的时候这样估计就没学上了！！！1

A

为什么大家都会做啊？？？？？？

考虑一种生成强连通块的方式：

可以发现，任意强连通块都能被生成。

（这个我不会证，而且一点也不显然吧，有没有老哥教我是怎么快速想到的啊？？？）

直接据此可以设计 O(3^npoly(n)) 的做法了。实现细节就是先把每条边较小的定向方式计入答案。

改一下 dp 方式，设 f(S) 表示最小代价，g(S,y,cur,0/1) 表示集合并上增广路是 S，增广路终点钦定了是 y，当前已经到了 cur，是不是不能连回来（如果增广路上第一个点且起点 = 终点，就不能连回来，因为不能有重边）。这就是 O(2^npoly(n))。

B

感觉这题比上题可做一点。比赛时差点想到正解，但是确实差点。vp 的时候没发现是“树上拓扑序计数”，dfs 的过程中直接把真实值搜出来了。

考虑 dfs 确定整个排列。可以发现，在 dfs 过程中只用确定 p_i 和当前的 p_1 的大小关系即可。钦定了大小关系之后计数就是树上拓扑序计数。爆搜过程不会太长，10 分钟左右就能搜完。

C

这个题太恐怖了，网上一共就找到 3 篇题解，三篇来回看才懂。而且还不敢说完全懂了。

Konig 定理：最小点覆盖 C = 最大匹配 M。

通过二分图匹配集合的拟阵性质，可以发现只需要求出在匹配的白点加入顺序意义下的最小字典序匹配即可。设为最优匹配，记最优匹配中的左部点集合为 best(L,R)。

考虑 Konig 定理的证明过程（这个证明过程多次直接运用（祭祀，Birthdays））：首先，最大匹配中每条边都至少有一端属于 C。故 C\ge M。下面构造一组点覆盖，大小恰为 M。

将二分图的边定向，匹配边方向 右 -> 左，非匹配边方向 左 -> 右。从左部不在匹配中的点开始 dfs，设 Z 为访问过的点集。设 L_+,R_+ 为两部与 Z 的交，L_-,R_- 为其补集。则 L_-\cup R_+ 是点覆盖：如果 L_+,R_- 之间有边，必须是匹配边（否则就能走过去了），又必须不是匹配边（如果从右边走过来，就不是 R_-）。

注意到 L_- 一定都是匹配点，R_+ 也一定是（否则，设是从 p dfs 到它的，那 p\to R_+ 有增广路）。还注意到每条匹配边两端要么都被 dfs 到要么都不被 dfs 到（分类讨论即可）。所以每条边两端恰有一端在 C 里面。Summarizing all the arguments above 即得证。

关于 L_+,R_+,L_-,R_- 有以下性质：

  1. 只保留 L_+,R_+，存在 R_+ 的完美匹配。（因为 R_+ 都是匹配点）
  2. 只保留 L_-,R_-，存在 L_- 的完美匹配。（同上）

同时 best(L,R) 还有性质：

  1. 设 L_k 为 L 中编号前 k 小的点，则 best(L_k,R)\subseteq best(L,R)。（拟阵性质）

用分治解决：设 f(L_1,L_2,R) 表示求出 best(L_1\cup L_2,R)，已知 L_2 中的点编号 <L_1，且全在最优匹配内部。

将 L_1 按编号大小均分为两部分 X,Y，将 (X\cup L_2),R 执行上面的 dfs 过程，分为 X_+,R_+,X_-,R_-。

由 3. 4. 知道，best(X_+,R_+) 一定属于答案中。调用 A=f(X_+\cap L_1,X_+\cap L_2,R_+) 可以求出 best(X_+,R_+)。

由 3. 4. 知道只需要把它并上 best(X_-\cup Y,R_-)，注意 X_- 一定属于答案中，调用 B=f(Y,X_-,R_-) 即可。最终返回 A\cup B。

这个分治过程有一个疑问：为什么要传入 L_2？通读整个算法，发现 L_2 的作用有：

  1. ”保证复杂度“，也即，尽可能利用已有的信息，减少”还未确定匹配否“的集合的大小（这个想法是成功的，因为的确每次递归 X 的大小都会减半）。
  2. 同时，将其一起下传避免了对 R 一侧到底匹配谁的讨论（我们知道它在答案，但不需要确定怎么在答案里的）。

实现上，找出匹配直接贪心；dfs 的过程可以用线段树模拟。