Complete the MST | Codeforces 1508C

题目链接

有一张 \(n\) 个点的无向完全图,其中 \(m\) 条边的边权已给定。

你需要给剩下的边确定边权,使得所有边的权值异或和为 \(0\)

求出所有方案中最小生成树权值的最小值。

\(n \le 2 \cdot 10^5,m \le \min\{2 \cdot 10^5,\binom n2-1\}\)

下面原图指给定的 \(m\) 条边构成的图,补图指剩下的边构成的图,MST 指最小生成树。

引理:最优解中补图至多有一条权值非 \(0\) 的边。

证明:考虑两条补图边 \(e_1,e_2\),它们的权值 \(w_1,w_2\) 都大于 \(0\)

  • 如果它们都不在 MST 上,把 \(e_1\) 权值变为 \(0\)\(e_2\) 权值异或上 \(e_1\) 权值,新的 MST 不会变劣。
  • 如果它们都在 MST 上,把 \(e_1\) 权值变为 \(0\)\(e_2\) 权值异或上 \(e_1\) 权值,因为 \(w_1 \oplus w_2 \le w_1 + w_2\),所以新的 MST 不会变劣。
  • 如果它们中的一条在 MST 上,一条不在,不妨设 \(e_1\)MST 上,把 \(e_1\) 权值变为 \(0\)\(e_2\) 权值异或上 \(e_1\) 权值,新的 MST 不会变劣。

综上,如果存在两条权值大于 \(0\) 的边,把其中一条的权值变为 \(0\),新的 MST 不会变劣。

所以补图中有一条特殊边的权值恰好为给定的 \(m\) 条边的权值异或和,其余边的权值均为 \(0\)

容易想到枚举一下特殊边在不在 MST 上。

先用 DFS 求出补图的生成森林,用 set 优化枚举未访问的点可以做到 \(O(m\log n)\) 的复杂度。

如果补图中存在环,那么补图中一定有边不在 MST 上,故特殊边一定不在 MST 上。把求出的生成森林加入原图后,答案即为该图的最小生成树,复杂度 \(O(m\log m)\)

如果不存在环,那么 \(n\) 就是 \(O(\sqrt m)\) 级别的,如果特殊边在 MST 上,直接用同样的做法;如果不在 MST 上,就需要枚举特殊边是哪一条,每次删去它再沿用以上做法,复杂度 \(O(m \log m + nm\alpha(n))\)。一个优化:用原图的最小生成树替代原图,复杂度降为 \(O(m\log m + n^2\alpha(n))=O(m\log m)\)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back

using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
int n, m, fa[N], xorsu, eid, tid;
int find(int x) { return x ^ fa[x] ? fa[x] = find(fa[x]) : x; }
int mrg(int u, int v) {
if((u = find(u)) ^ (v = find(v))) return fa[u] = v;
return 0;
}
vector <int> G[N];
struct edge {
int u, v, w;
bool operator <(const edge& b)const {
return w < b.w;
}
} e[N], t[N];
set <int> s;
void dfs(int u) {
s.erase(u);
For(i, 0, G[u].size() - 1) {
int v = G[u][i], nxt = G[u][i + 1];
while(!s.empty() && *s.rbegin() > v) {
int vv = *s.upper_bound(v);
if(vv >= nxt) break;
t[++tid] = {u, vv}, dfs(vv);
}
}
}
int main() {
cin >> n >> m;
rep(i, 1, m) {
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w), xorsu ^= e[i].w;
G[e[i].u].pb(e[i].v), G[e[i].v].pb(e[i].u);
}
rep(i, 1, n) G[i].pb(0), G[i].pb(n + 1), sort(G[i].begin(), G[i].end()), s.insert(i);
while(!s.empty()) dfs(*s.begin());
sort(e + 1, e + m + 1);
rep(i, 1, n) fa[i] = i;
rep(i, 1, m) if(mrg(e[i].u, e[i].v)) e[++eid] = e[i];
if(tid < n * (n - 1ll) / 2 - m) {
rep(i, 1, n) fa[i] = i;
rep(i, 1, tid) mrg(t[i].u, t[i].v);
ll as = 0;
rep(i, 1, eid) if(mrg(e[i].u, e[i].v)) as += e[i].w;
cout << as;
} else {
ll as = 1e18;
rep(i, 0, tid) {
rep(j, 1, n) fa[j] = j;
rep(j, 1, tid) if(j ^ i) mrg(t[j].u, t[j].v);
ll su = i ? 0 : xorsu;
rep(j, 1, eid) if(mrg(e[j].u, e[j].v)) su += e[j].w;
as = min(as, su);
}
cout << as;
}
return 0;
}