CF1508C Complete the MST 题解

CF1508C

给定一个有 \(n\) 个节点的完全图，其中 \(m\) 条边有给定的边权，剩下的没有给定。

你需要给所有没有给定边权的边赋上非负整数边权，使得所有边的边权的异或和等于 \(0\)。

我们认为这个图的“丑陋值”为这个图的最小生成树的边权之和，求所有可能的赋值方案中，“丑陋值”的最小值。

\(2\leq n\leq2\times10^5;0\leq m\leq\min(2\times10^5,\dfrac{n\times(n-1)}{2}-1)\)。至少有一条边是没有给定边权的。

对于第 \(i\) 条给定边权的边，若用 \(u_i,v_i,w_i\) 表示所连接的两个节点和边权，则 \(1\leq u_i,v_i\leq n;u_i\not=v_i;1\leq w_i<2^{30};\) 不会有边在输入中出现多次。

• 我们可以把给定的边分为 \(3\) 类

  1. 一定会加入 MST 的边

  2. 一定不会加入 MST 的边

  3. 可能加入 MST 的边

• 显然的，我们可以只选择一条边为整张图边权的异或值，而剩下的边都为 \(0\)，这一定是最优的

• 关键在于选择哪条边作为有值的边

• 如果说除去给定的边外的边构成了一个环，那么我们只需要选择这个环上的任意一条边作为有值的边即可

• 否则此时给定的边一定在原图中非常密集，换句话说就是 \(n\) 会很小，大概在 \(\sqrt m\) 量级

• 此时我们考虑用 \(1,2\) 类边构成的环来代替这条边，只需要把一二种边加入并查集，对没给定的边判断是否在同一个联通块内

• 最终复杂度 \(O(n \log n)\)