题解 P7323 【[WC2021] 括号路径】

鏡音リン · 2021-02-05 15:07:50 · 题解

场外口胡简要题解（update：改了个小笔误）

记一条从 x 到 y，括号为 w 的边为 (x,y,w)，与 w 对应的另一个括号是 -w。题目中给了一个非常好的性质：(x,y,w) 和 (y,x,-w) 是成对存在的。那么可以发现： 任意一条合法路径的逆路径相当于把括号序列翻转，同时每个括号变成对应另一个括号，得到的还是合法路径。换句话说，可达一定是双向可达。

如果一个点 x 存在两条括号相同的出边 (x,a,w) 和 (x,b,w)，且 w 是右括号，那么 a\to x\to b 和 b\to x\to a 都是长度为 2 的合法路径，即 a,b 双向可达。注意到在一个合法括号序列中插入另一个合法括号序列得到的仍然是合法括号序列，可以把 a,b 合并成一个点处理。由于上面的性质说明合并后新图中的合法路径一定对应着一条原图中的合法路径。一直找这样的两条边并合并，直到找不到的时候，说明此时已没有长度为 2 的合法路径，显然不存在任何合法路径，算法结束。

具体实现时，每个点维护其上括号是左括号的边，以及它合并之前是多少个点用于计算答案。由于合并后一个点上每种括号的边只有一条，可以先记录下开始就有的合并，然后用一个哈希表维护上面的边，括号作为键，边的终点作为值。合并点可以使用并查集，用启发式合并的办法处理上面的边，把边少的合并到多的上。一次合并可能引起其他的合并，可以用队列处理。根据启发式合并的复杂度分析，总复杂度为 O(m\log m)。如果用的不是哈希表而是 std::map，会变成O(m\log^2 m)，可能会超时。