神秘图论技巧

· · 个人记录

给定一个点双连通分量中的两个点 u,v 和一条边 e，要求找到一条 u\rightarrow v 的简单路径经过 e。

以 u 为根求一棵 dfs 树，我们强制 e 为一条树边。

如果 e 在 u 到 v 的树路径 P 上，那么直接选择 P 即可。

否则我们需要给 P 异或上一个简单环 C，只要求：

设 x 为 e 在树上较深的端点，y 为 v 和 x 的 LCA。

因为是 dfs 树，所以每一条非树边都是返祖边，并且每一条返祖边都对应了一个简单环。

首先我们找到下端点在 x 子树中（包括 x）上端点最浅的返祖边，设 t 初始为这条返祖边的上端点。

然后我们每次考虑 t 的所有儿子，它们之中恰好有一个满足 x 在它的子树内，设 t 的这个儿子为 t_1。那么我们找到下端点在 t_1 的子树中（包括 t_1）且上端点最浅的返祖边，并将 t 变为这条返祖边的上端点。如果此时 t 已经严格在 y 上方，那么就停止。

考虑这个过程中经过的所有返祖边。我们可以归纳地证明这些返祖边所对应的简单环的异或也是一个简单环。每次新加入的简单环与之前异或出来的简单环的交集为树上的一条非空简单路径。

同时因为我们一旦跳到 y 上方就停止，所以这个简单环与 P 的交集一定是从 y 开始向上的一条非空简单路径。

直接将这个简单环作为 C 即可得到合法解。

时间复杂度 O(n+m)。

给定一个有向图，每次你可以删除一个环，你需要构造一组操作使得最后得到一个 DAG。

算法一：

如果一个点已经没有出度，那么它一定不会出现在某个环中，在接下来的过程中不需要考虑这个点，将它从图中删掉即可。

否则对于每个点找任意一条出度，此时可以得到一个内向基环森林，将其中的环删除即可。

不断执行这个过程直到图为空，我们就得到了一种删除环的方法。

时间复杂度 O(n+m)。

算法二：

直接进行 dfs，维护当前从起点开始走的路径 P。设 P 中最后一个点为 u。

如果 u 没有出边，那么设 P 中 u 的上一个点为 v，此时我们需要回溯到 v。回溯的同时我们可以将 e 删除，因为它不可能出现在一个环中。

否则任意找 u 的一条出边 (u,v)，如果 v 在 P 中出现过，那么我们找到了一个环，将它删除并回溯到 v 即可。

枚举每个点作为起点都进行一次上述过程即可。

可以发现每条边只会访问一次，因为在回溯的时候所有从 P 中弹出的边都立刻被删除了。因此时间复杂度为 O(n+m)。

如果按照固定的顺序访问一个点的出边，那么一个点的出边中被删除的一定是一段前缀。因此可以直接采用当前弧优化来实现，即记录每个点第一条没有被删除的出边。

给定一个二分图，点带权，求一组匹配使得点权和最大。

不加证明地给出结论：