Loading...

洛谷P1269 信号放大器

check评论:0 条 remove_red_eye浏览量:417 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-12-22

我们用贪心

每个点记录上一个加了放大器的点到他的距离,以及到他父亲的距离,如果距离大了我们就加信号放大器,然后更新上一个距离为$0$即可,最后统计答案

#include <bits/stdc++.h>
using namespace std;
int head[20010],cnt,fa[20010],dp[20010],qaq,ans;
struct edge
{
    int next,to,dis;
}e[20010];
void add(int u,int v,int dis)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].dis=dis;
    head[u]=cnt;    
}
void dfs(int u,int f)
{
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==f)
        {
            continue; 
        }
        fa[v]=e[i].dis;
        dfs(v,u);
        dp[u]=max(dp[v]+e[i].dis,dp[u]);
    }
    if(dp[u]+fa[u]>qaq)
    {
        ans++;
        dp[u]=0;
    }
}
int main()
{
    int n,maxn=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int k;
        scanf("%d",&k);
        for(int j=1;j<=k;j++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            add(i,a,b);
            maxn=max(maxn,b);
        }
    }
       cin>>qaq;
    if(maxn>=qaq)
    {
        cout<<"No solution.";
        return 0;
    }
    dfs(1,1);
    cout<<ans;
    return 0;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名