题解：P1269 信号放大器

· · 题解

题意简述

一棵以服务器（结点 1）为根的树，每条边有衰减量。信号从服务器以强度 k 出发，过一条边强度减去其衰减量，强度降到 0 及以下就无法再传。在某结点装放大器可把信号还原成 k。求让信号传遍全树所需的最少放大器数；无法做到则输出 No solution.。

解题思路

树形 DP。设 f_u 为要让子树 u 全部收到信号、信号到达 u 处所需的最小强度，叶子 f_u=1（能被收到即可）。

自底向上，对 u 的每个儿子 v（边权 w）有两种选择：

  1. 不放大 v：u 要把强度 f_v 送到 v，自身强度需不小于 f_v+w，该儿子对 f_u 的贡献即 f_v+w；
  2. 放大 v：当 f_v+w>k（u 满强度 k 也送不到 v）时只能在 v 装放大器，v 被还原成 k 后自给自足，u 只需把信号送达 v，贡献降为 w+1，放大器数加一。

于是 f_u=\max\bigl(1,\max_v(\text{各儿子贡献})\bigr)，按需放大保证 f_u\le k。服务器自带强度 k，从它 DFS 一遍累计放大器数即为答案。

只要有一条边的衰减量不小于 k，这条边永远跨不过去，直接输出 No solution.。

时间复杂度为 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=20005;
int k,ans;
int f[N];
bool vis[N];
vector<pair<int,int>> G[N];
void dfs(int u)
{
    vis[u]=1;
    f[u]=1;
    for(auto [v,w]:G[u])
    {
        if(vis[v])continue;
        dfs(v);
        if(f[v]+w>k)
        {
            ans++;
            f[u]=max(f[u],w+1);
        }
        else f[u]=max(f[u],f[v]+w);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    int mx=0;
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        while(t--)
        {
            int v,w;
            cin>>v>>w;
            G[i].push_back({v,w});
            mx=max(mx,w);
        }
    }
    cin>>k;
    if(mx>=k)
    {
        cout<<"No solution.\n";
        return 0;
    }
    dfs(1);
    cout<<ans<<'\n';
    return 0;
}