【题解】HarkerRank - Matrix

Posted on In Disqus:

题目

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

题意

在一棵有边权的树上，要求去掉一些边，使得给定的若干个点之间两两不连通，求这些边的最小边权和。

题解

  • 树形 dp
  • \(f[u]\) 表示子树上所有给定点与当前点不连通的最小代价（自己解决所有问题）。
  • \(g[u]\) 表示子树上恰有一个给定点与当前点联通的最小代价（自己几乎解决了问题，但还要父亲帮忙）。
  • \(t_v = \min\{w_{uv}+g[v],f[v]\}​\) 表示解决儿子 \(v​\) 的最小代价。
  • \(s=\sum t_v\) 表示解决除自己外所有问题的代价。
  • \(m = \max\{t_v-g[v]\}\) 表示所有儿子中少解决一个所能省下的最大代价。
  • 分情况
    • 如果当前结点是需要隔离的：\(f[u]=\inf, g[u]=s\)
    • 如果当前点不需要隔离：\(f[u]=s, g[u]=s-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
#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 = 1E6 + 100;
const LL INF = 1E18;
LL f[maxn], g[maxn]; // f: include, g: exclude
struct E {
    LL to, d;
};
bool b[maxn];
vector<E> G[maxn];

void go(LL u, LL fa) {
    LL s = 0, m = 0;
    for (E& e: G[u]) {
        LL v = e.to;
        if (v == fa) continue;
        go(v, u);
        LL t =  min(f[v], g[v] + e.d);
        s += t;
        m = max(m, t - g[v]);
    }
    if (b[u]) { f[u] = INF; g[u] = s; }
    else { f[u] = s; g[u] = s - m; }
}

int main() {
    int n, k;
    cin >> n >> k;
    FOR (_, 1, n) {
        LL u, v, d;
        scanf("%lld%lld%lld", &u, &v, &d);
        G[u].push_back({v, d});
        G[v].push_back({u, d});
    }
    while (k--) {
        LL u; scanf("%lld", &u);
        b[u] = true;
    }
    go(1, -1);
    cout << g[1] << endl;
}