Luogu

算法

树形DP。

设$g[i]$表示以i为根的子树所需的最小信号强度,$f[i]$表示以i为根的子树所需的最少信号放大器数。

那么接下来分情况讨论一下。

  • 若i是叶子节点,则$g[i]=1,f[i]=0$。
  • 若i不是叶子节点,则$g[i]=max(g[Son_i]+dis[i][Son_i]),f[i]=sum(f[Son_i])$。
  • i!=0 && 初始信号-dis[Father_of_i][i]<g[i],则需要新建一个信号放大器,即$f[i]++,g[i]=1$。

然后直接DP就好了。

注意输入是有向图。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
int n,s;
struct Edge { int v,w,nxt; } e[40010];
int head[20010],cnt;
inline void addEdge(int u,int v,int w) {
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int g[20010]; //g[i]表示以i为根的子树所需的最小信号强度
int f[20010]; //f[i]表示以i为根的子树所需的最少信号放大器数
bool vis[20010];
inline void upload(int& a,const int& b) { if (b>a) a=b; }
inline void Dfs(int u) {
    vis[u]=true;
    g[u]=-1; f[u]=0; int fu;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        if (vis[v]) { fu=i; continue; }
        if (w>=s) { printf("No solution.\n"); exit(0); }
        Dfs(v); upload(g[u],g[v]+w); f[u]+=f[v];
    }
    if (g[u]==-1) { g[u]=1; f[u]=0; }
    else if (u!=1&&s-e[fu].w<g[u]) { g[u]=1; f[u]++; }
}
int main() {
    n=read();
    for (re int u=1;u<=n;u++) {
        int k=read();
        while (k--) {
            int v=read(),w=read();
            addEdge(u,v,w);
        }
    }
    s=read(); Dfs(1); printf("%d\n",f[1]);
    return 0;
}
最后修改:2019 年 09 月 24 日 12 : 55 PM