【题解】HackerRank - Roads in HackerLand

Posted on Edited on In Disqus:

题目

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("");
}