文档章节

P2279 [HNOI2003]消防局的设立

o
 osc_x4h57ch8
发布于 2018/04/24 12:28
字数 768
阅读 0
收藏 0
ios

精选30+云产品,助力企业轻松上云!>>>

题目描述

2020年,人类在火星上建立了一个庞大的基地群,总共有n个基地。起初为了节约材料,人类只修建了n-1条道路来连接这些基地,并且每两个基地都能够通过道路到达,所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条道路的话,我们称基地A到基地B的距离为d。

由于火星上非常干燥,经常引发火灾,人类决定在火星上修建若干个消防局。消防局只能修建在基地里,每个消防局有能力扑灭与它距离不超过2的基地的火灾。

你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时,消防队有能力及时扑灭火灾。

输入输出格式

输入格式:

输入文件名为input.txt。

输入文件的第一行为n (n<=1000),表示火星上基地的数目。接下来的n-1行每行有一个正整数,其中文件第i行的正整数为a[i],表示从编号为i的基地到编号为a[i]的基地之间有一条道路,为了更加简洁的描述树状结构的基地群,有a[i]<i。

输出格式:

输出文件名为output.txt

输出文件仅有一个正整数,表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的火灾。

输入输出样例

输入样例#1: 
6
1
2
3
4
5
输出样例#1: 
2

 

Solution:

  本题和某次月赛的题目将军令简直一毛一样(~手动滑稽~)。

  由于是一棵树,直接以$1$为根节点建树并处理出每个节点的深度,将节点按深度从大到小排序,每次贪心地去从最深的没有被标记的点往前走$4$步(因为控制半径为$2$,所以找出范围边界),经过的点打上标记,累加搜索次数就是答案。

代码:

 

#include<bits/stdc++.h>
#define il inline
#define ll long long
using namespace std;
const int N=10005;
int n,h[N],cnt,to[N],net[N],ans;
bool vis[N],ct[N];
struct point{
    int id,dis;
    bool operator <(point a){if(dis==a.dis)return id<a.id;return dis<a.dis;}
}a[N];
il void add(int x,int y){to[++cnt]=y,net[cnt]=h[x],h[x]=cnt;}
il void dfs(int u,int last){
    for(int i=h[u];i;i=net[i])
        if(last!=to[i]){
                a[to[i]].dis=a[u].dis+1;
                a[to[i]].id=to[i];
                dfs(to[i],u);
        }
}
il void dfs1(int u,int k){
    if(k<0)return;
    vis[u]=1,ct[u]=1;
    for(int i=h[u];i;i=net[i])
        if(!vis[to[i]])dfs1(to[i],k-1);
    vis[u]=0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    int u;a[1].id=1,a[1].dis=0;
    for(int i=2;i<=n;i++)cin>>u,add(u,i),add(i,u);
    dfs(1,0);
    sort(a+1,a+n+1);
    for(int i=n;i>=1;i--)
        if(!ct[a[i].id]){
            ans++;
            dfs1(a[i].id,4);
        }
    cout<<ans;
    return 0;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

unity的UGUI之中锚点(Anchors)和中心点(Pivot)、Shift和Alt键功能

在UGUI的控件属性之中,最上方的Rect Transform一栏可以看到锚点和中心点: 锚点Anchors 控件用于定位自身的基准点 可以点击左上角的方框,在其中选择锚点的不同方式: 注意图中,黄色的小点...

路过暴风
今天
7
0
如何将div放置在其容器的底部? - How can I position my div at the bottom of its container?

问题: Given the following HTML: 鉴于以下HTML: <div id="container"> <!-- Other elements here --> <div id="copyright"> Copyright Foo web designs </div> </div> I would like #cop......

富含淀粉
今天
10
0
Distinct()与lambda? - Distinct() with lambda?

问题: Right, so I have an enumerable and wish to get distinct values from it. 是的,所以我有一个可枚举的,并希望从中获得不同的值。 Using System.Linq , there's of course an ext......

法国红酒甜
今天
16
0
学习编写编译器[关闭] - Learning to write a compiler [closed]

问题: Preferred languages : C/C++, Java, and Ruby. 首选语言 :C / C ++,Java和Ruby。 I am looking for some helpful books/tutorials on how to write your own compiler simply for......

技术盛宴
今天
17
0
OSChina 周一乱弹 —— 毛巾又怎么样?!我在乎的是大姐姐温柔的怀抱!

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @薛定谔的兄弟 :分享洛神有语创建的歌单「我喜欢的音乐」: 《雨 因你而下,于你而止》- Seto 手机党少年们想听歌,请使劲儿戳(这里) @Dan...

小小编辑
今天
54
2

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部