【题解】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 ge

基本算法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 }

VIEw Code 总结

以上是内存溢出为你收集整理的【题解】Luogu P1269 信号放大器 贪心全部内容，希望文章能够帮你解决【题解】Luogu P1269 信号放大器 贪心所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。