【题解】Luogu P1269 信号放大器 贪心

基本算法2-1

贪心选择放置放大器的点

设$dep[i]$表示$i$子树内离他最远的距离，$dis[i]$表示$i$到他父亲的距离

只有当$dep[i]+dis[i]>初始值$才需要一个放大器，然后把这个点的dep[i]清零

这样贪心一定最优

code

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 namespace gengyf{
 4 #define ll long long
 5 const int maxn=1e5+10;
 6 const int mod=1e9;
 7 inline int read(){
 8     int f=1,x=0;char s=getchar();
 9     while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();}
10     while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();}
11     return f*x;
12 }
13 int n,p,fl,ans;
14 struct edge{
15     int nxt,to,w;
16 }e[maxn*2];
17 int head[maxn],cnt,dis[maxn],dep[maxn];
18 inline void add(int from,int to,int w){
19     e[++cnt].to=to;e[cnt].w=w;e[cnt].nxt=head[from];head[from]=cnt;
20 }
21 void dfs(int x,int fa){
22     for(int i=head[x];i;i=e[i].nxt){
23         if(e[i].to!=fa){
24             dis[e[i].to]=e[i].w;
25             dfs(e[i].to,x);
26             dep[x]=max(dep[e[i].to]+e[i].w,dep[x]);
27         }
28     }
29     if(dis[x]+dep[x]>p){
30         ans++;dep[x]=0;
31     }
32 }
33 int main(){
34     n=read();
35     for(int i=1;i<=n;i++){
36         int k;k=read();
37         for(int j=1;j<=k;j++){
38             int v,w;
39             v=read();w=read();add(i,v,w);
40             fl=max(fl,w);
41         }
42     }
43     p=read();
44     if(fl>=p){
45         cout<<"No solution."<<endl;
46         return 0;
47     }
48     dfs(1,1);
49     printf("%d",ans);
50     return 0;
51 }
52 }
53 signed main(){
54   gengyf::main();
55   return 0;
56 }