k半径覆盖问题

阳光穿透心脏的1/2处 2021-11-29 15:04 183阅读 0赞

# 题意 #

一个点可以覆盖半径2以内的的点，最少多少点可以全覆盖（可以延伸为k半径）

预处理出每个点深度，从最深的点开始网上覆盖，dis数组表示最近的覆盖中心点的距离，大于2（k）时，把他的2（k）代设成覆盖中心（贪心思想，保证最远且刚好能覆盖当前点）

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll mod=998244353;
    const int maxn=500005;
    int n;
    int dis[100005],fa[100005],dep[100005],id[100005],ant;
    bool cmp(int a,int b)
    {
        return dep[a]>dep[b];
    }
    int main()
    {
        scanf("%d",&n);
        id[1]=1;
        dis[0]=dis[1]=maxn;
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&fa[i]);
            dep[i]=dep[fa[i]]+1;
            id[i]=i;
            dis[i]=maxn;
        }
        sort(id+1,id+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            int now=id[i];
            int f=fa[now];
            int gf=fa[fa[now]];
            dis[now]=min(dis[now],dis[f]+1);
            dis[now]=min(dis[now],dis[gf]+2);
            if(dis[now]>2)
            {
                ant++;
                dis[gf]=0;
                dis[fa[gf]]=min(dis[fa[gf]],1);
                dis[fa[fa[gf]]]=min(dis[fa[fa[gf]]],2);
            }
        }
        printf("%d\n",ant);
        return 0;
    }

转载于:https://www.cnblogs.com/Diliiiii/p/11222529.html

发表评论取消回复

表情：

评论列表（有 0 条评论，183人围观）

还没有评论，来说两句吧...

相关阅读

相关区间覆盖问题

1）区间完全覆盖问题问题描述：给定一个长度为m的区间，再给出n条线段的起点和终点（注意这里是闭区间），求最少使用多少条线段可以将整个区间完全覆盖样例：区间

一时失言乱红尘/ 2022年07月26日 04:09/ 0 赞/ 156 阅读

相关区间覆盖问题

Problem Description 用i来表示x坐标轴上坐标为\[i-1，i\]的长度为1的区间，并给出n（1≤n≤200）个不同的整数，表示n个这样的区间。现在要求

野性酷女/ 2022年07月13日 03:57/ 0 赞/ 190 阅读

相关区间覆盖问题

Problem Description 用i来表示x坐标轴上坐标为\[i-1，i\]的长度为1的区间，并给出n（1≤n≤200）个不同的整数，表示n个这样的区间。现在

末蓝、/ 2022年07月12日 02:05/ 0 赞/ 226 阅读

相关区间覆盖问题

区间覆盖问题 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [ Statistic]

今天药忘吃喽~/ 2022年06月17日 09:49/ 0 赞/ 173 阅读

相关样式覆盖问题

最近做前端使用外源框架，需要对框架本身使用的样式进行本地调适，这就涉及到了优先的问题。一般，样式写在外部文件，然后引入外部文件。通过chorme控制台的Element工具定

￡神魔★判官ぃ/ 2022年06月01日 06:43/ 0 赞/ 215 阅读

相关 JDK覆盖问题

原文：[https://blog.csdn.net/just\_coming\_here/article/details/51775909][https_blog.csdn.n

川长思鸟来/ 2022年05月18日 04:40/ 0 赞/ 166 阅读

相关区间覆盖问题

Problem Description 用i来表示x坐标轴上坐标为\[i-1，i\]的长度为1的区间，并给出n（1≤n≤200）个不同的整数，表示n个这样的区间。现在要求

谁践踏了优雅/ 2022年05月16日 13:08/ 0 赞/ 164 阅读

相关动态规划之直线k覆盖问题

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4

阳光穿透心脏的1/2处/ 2022年04月22日 02:16/ 0 赞/ 180 阅读

相关区间覆盖问题

区间覆盖问题 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Problem

逃离我推掉我的手/ 2022年02月15日 04:47/ 0 赞/ 244 阅读

相关 k半径覆盖问题

题意一个点可以覆盖半径2以内的的点，最少多少点可以全覆盖（可以延伸为k半径）预处理出每个点深度，从最深的点开始网上覆盖，dis数组表示最近的覆盖中心点的距离，大于2

阳光穿透心脏的1/2处/ 2021年11月29日 15:04/ 0 赞/ 184 阅读