【题解】HackerRank - Roads in HackerLand

题目

https://www.hackerrank.com/challenges/johnland/problem

题意

给一个联通的无向图,求所有点对之间的最小距离和。其中每条边的距离都是 2 的幂且互不相同。

题解

  • 每条边距离为 2 的幂且不相同,意味着选择长的边很可能是不好的。
  • 这道题跑最短路显然不大可能,因为需要求所有点对的距离和。最优解是最小生成树,接下来来证明。
  • 假设最优解不是最小生成树,那么去掉其中长度最长的边(长度为 \(k\))后再增加若干条长度小于 \(k\) 的边仍能使其联通。先去掉最长的边,那么有一些点对会无法联通,这些点对的距离至少为 \(2^k\),现在增加一些边使其联通,那么这些点对的距离至多是 \(2^0+2^1+2^2+\dots+2^{k-1}<2^k\),从而得到一个更优解,所以假设不成立。
  • 既然是最小生成树,那么需要求一下这棵树上每条边的贡献,这个问题就比较简单了,跑一边 dfs 即可。

代码

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
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (false)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 2E5 + 100;
int n, m;
struct E {
int u, v, d;
};
struct EE {
int to, d;
};
vector<E> edges;
int fa[maxn];
vector<EE> G[maxn];
LL ans[maxn];
int findset(int x) { return fa[x] == -1 ? x : fa[x] = findset(fa[x]); }

int dfs(int u, int fa) {
int sz = 1;
for (EE& e: G[u]) {
int v = e.to;
if (v == fa) continue;
int t = dfs(v, u);
ans[e.d] += 1LL * t * (n - t);
sz += t;
}
return sz;
}

int main() {
memset(fa, -1, sizeof fa);
cin >> n >> m;
FOR (_, 0, m) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
edges.push_back({u, v, d});
}
sort(edges.begin(), edges.end(), [](const E& a, const E& b)->bool{ return a.d < b.d; });
int C = n - 1;
for (E& e: edges) {
if (!C) break;
int fu = findset(e.u), fv = findset(e.v);
if (fu != fv) {
--C;
fa[fu] = fv;
G[e.u].push_back({e.v, e.d});
G[e.v].push_back({e.u, e.d});
}
}
dfs(1, -1);
FOR (i, 0, maxn)
if (ans[i] > 1) {
ans[i + 1] += ans[i] >> 1;
ans[i] &= 1;
}
int last = maxn - 1;
while (!ans[last]) --last;
FORD (i, last, -1)
printf("%lld", ans[i]);
puts("");
}