信号放大器

题意

给一棵树，1 号点是服务器。

服务器发出初始强度为 S 的信号，经过一条边会减去该边的衰减量。

如果在某个节点安装放大器，那么这个节点收到一个强度大于 0 的信号后，会把它恢复成初始强度 S 再继续往下传。

要求用最少的放大器让整棵树所有节点都能收到信号；如果不可能做到，输出 No solution.

思路

先看一个可以直接验证想法的朴素解：

cpp

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;
const int MAXM = 55;

int n, S;
int head[MAXN], to[MAXM], nxt[MAXM], cost[MAXM], edge_cnt;
int parent_node[MAXN], parent_cost[MAXN];
int order_list[MAXN], order_cnt;
bool chosen[MAXN];

void add_edge(int u, int v, int w) {
    edge_cnt++;
    to[edge_cnt] = v;
    cost[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

void build_tree_order() {
    static int q[MAXN];
    int l = 0, r = 0;
    q[r++] = 1;
    parent_node[1] = 0;
    order_cnt = 0;
    while (l < r) {
        int u = q[l++];
        order_list[order_cnt++] = u;
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (v == parent_node[u]) {
                continue;
            }
            parent_node[v] = u;
            parent_cost[v] = cost[i];
            q[r++] = v;
        }
    }
}

bool check_mask() {
    static int strength[MAXN];
    strength[1] = S;

    for (int idx = 1; idx < order_cnt; idx++) {
        int u = order_list[idx];
        int p = parent_node[u];
        strength[u] = strength[p] - parent_cost[u];
        if (strength[u] <= 0) {
            return false;
        }
        if (chosen[u]) {
            strength[u] = S;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int u = 1; u <= n; u++) {
        int k;
        cin >> k;
        for (int i = 0; i < k; i++) {
            int v, w;
            cin >> v >> w;
            if (u < v) {
                add_edge(u, v, w);
                add_edge(v, u, w);
            }
        }
    }
    cin >> S;

    build_tree_order();

    // brute.cpp：枚举所有非根节点是否安装放大器，只适合很小数据对拍。
    int total = n - 1;
    int best = -1;

    for (int mask = 0; mask < (1 << total); mask++) {
        int cnt = 0;
        for (int i = 0; i < total; i++) {
            chosen[i + 2] = ((mask >> i) & 1);
            if (chosen[i + 2]) {
                cnt++;
            }
        }
        if (best != -1 && cnt >= best) {
            continue;
        }
        if (check_mask()) {
            best = cnt;
        }
    }

    if (best == -1) {
        cout << "No solution.\n";
    } else {
        cout << best << '\n';
    }

    return 0;
}

brute.cpp 直接枚举所有非根节点是否安装放大器，只适合很小数据验证。

正式解的关键是把树根定在 1 号点，然后自底向上考虑。

对一个节点 u，父节点真正关心的不是整个 u 子树细节，而只是：

这棵子树里最危险的那条路径
在当前已经决定的放大器布置下
它还会向上“拖”出多少未被截断的衰减

记这个值为 remain[u]。

现在考虑 u 的儿子 v，边权为 w。

如果 remain[v] + w < S，说明这棵子树还可以继续和更高层共用一次信号，不需要立刻装放大器。

如果 remain[v] + w >= S，那就说明：

这棵子树里已经存在一条路径
再经过边 (u,v) 后，累计衰减就会达到或超过 S

此时不在 v 这里放放大器的话，这条路径必然断掉。

而放在更下面已经晚了，放在更上面也没意义，因为父节点本来发出的就是满强度。

所以这里只能在 v 处安装一个放大器。

于是后序贪心就出来了：

先处理儿子
计算 need = remain[v] + w
若 need >= S，答案加一，并把这棵子树对当前点的贡献重置成 w
否则把 need 参与当前点最大值

另外如果某条边本身 w >= S，那么信号连这个儿子节点都到不了，直接无解。

代码

cpp

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20005;
const int MAXM = 40005;

int n, S;
int head[MAXN], to[MAXM], nxt[MAXM], cost[MAXM], edge_cnt;
int parent_node[MAXN], parent_cost[MAXN];
int order_list[MAXN], order_cnt;
int remain_need[MAXN];
int answer;
bool impossible;

void add_edge(int u, int v, int w) {
    edge_cnt++;
    to[edge_cnt] = v;
    cost[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

void build_tree_order() {
    static int q[MAXN];
    int l = 0, r = 0;
    q[r++] = 1;
    parent_node[1] = 0;
    parent_cost[1] = 0;
    order_cnt = 0;

    while (l < r) {
        int u = q[l++];
        order_list[order_cnt++] = u;
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (v == parent_node[u]) {
                continue;
            }
            parent_node[v] = u;
            parent_cost[v] = cost[i];
            q[r++] = v;
        }
    }
}

void solve() {
    build_tree_order();
    answer = 0;
    impossible = false;

    for (int idx = order_cnt - 1; idx >= 0; idx--) {
        int u = order_list[idx];
        int best = 0;

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (v == parent_node[u]) {
                continue;
            }

            int w = cost[i];
            if (w >= S) {
                impossible = true;
                return;
            }

            // 子树里最长的“还没在途中放大”的链，继续经过这条边往上走。
            int need = remain_need[v] + w;

            if (need >= S) {
                // 如果再往上走就断掉，只能在儿子 v 这里安装放大器。
                answer++;
                // 安装后从 u 往下到 v 这条边仍然要承受 w 的衰减。
                if (w > best) {
                    best = w;
                }
            } else {
                if (need > best) {
                    best = need;
                }
            }
        }

        remain_need[u] = best;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int u = 1; u <= n; u++) {
        int k;
        cin >> k;
        for (int i = 0; i < k; i++) {
            int v, w;
            cin >> v >> w;
            if (u < v) {
                add_edge(u, v, w);
                add_edge(v, u, w);
            }
        }
    }
    cin >> S;

    solve();

    if (impossible) {
        cout << "No solution.\n";
    } else {
        cout << answer << '\n';
    }

    return 0;
}

复杂度

每条边只处理常数次，所以时间复杂度：

$O(n)$

空间复杂度：

$O(n)$

总结

这题的关键不是枚举放大器位置，而是看出：

每个子树只需要向上汇报一个“最坏剩余衰减”
一旦再过父边就会失效，就必须在儿子处放放大器

这样整题就变成了一个非常干净的后序贪心树 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

代码

复杂度

总结

一图流解析