P1269 信号放大器 题解

· · 题解

前言

树形 DP.

个人感觉黄绿级别，没有辣么难。

正文

先特判最大衰减度是否大于服务器信号强度。

然后开始考虑 DP.

设 f_u, d 为以节点 u 为根，强度为 d 的子树的放大器数目, f_{u, d, 0} 是 u 不放放大器，f_{u, d, 1} 是 u 放了放大器。

则（w_{u->v} 为从 u 到 v 的边长）：

f_{u, 0} = \Bigg\{^{\sum\min_{u \ne v}\{f_{v, d, 0}, f_{v, d, 1}\} \quad (d > w_{u->v})}_{\infty \quad (d \le w_{u->v})} f_{u, 1} = \sum \min_{u \ne v}\{f_{v, d, 0}, f_{v, d, 1}\} + 1

那么问题迎刃而解。

总复杂度: \mathcal{O}(N^2). 可以通过此题。

代码

你们最想要的..

Talk is\color{white}\text{n't} cheap, \color{white}\text{Don't} show me the code...

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

struct Terminal {
    int to, val;
};

int N, M, maxdelta;
vector<Terminal> graph[20005];
int f[20005][2];

void dfs(int u, int fa, int db);

signed main()
{
    cin >> N;
    for(int i = 1; i <= N; i ++)
    {
        int K;
        cin >> K;
        for(int j = 1; j <= K; j ++)
        {
            int v, w;
            cin >> v >> w;
            graph[i].push_back({v, w});
            maxdelta = max(maxdelta, w); 
        }
    }

    cin >> M;
    if(M <= maxdelta) {puts("No solution."); return 0;}
    dfs(1, -114514, M);
    cout << min(f[1][0], f[1][1]);
    return 0;
}

void dfs(int u, int fa, int db)
{
    f[u][1] = 1;
    f[u][0] = 0;
    for(int i = 0; i < graph[u].size(); i ++)
    {
        int v = graph[u][i].to;
        int w = graph[u][i].val;
        if(v == fa) 
            continue;

        if(db > w)
            dfs(v, u, db - w), f[u][0] += min(f[v][0], f[v][1]);
        else
            f[u][0] = 1e7;

        dfs(v, u, M - w);
        f[u][1] += min(f[v][0], f[v][1]);
    }
}

后言

没有使用链式前向星，望谅解。