[HNOI2003]消防局的设立
题目描述
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
这道题本来应该是考贪心的,但由于距离为2,所以树形dp也可以做
本篇主要讲贪心
首先,看到题目中的这句话
每个消防局有能力扑灭与它距离不超过2的基地的火灾。
这要求我们至少在底层的叶子结点一定要有消防局去覆盖它,这个时候有几个选择
- 自己本身
- 父亲节点
- 兄弟节点
- 祖父节点
很显然,前三种情况都可以被最后一种情况包括,即选择最后一种策略不会更劣,那么我们确定了贪心思路:如果我们确定了一个节点需要被覆盖,那么在它的祖父节点设立消防局就可以了
那么现在问题就是怎么找出那些需要被覆盖的节点?
我们用一个数组dis[i]表示i节点与离i最近的消防局之间的距离
初始值因为没有设立消防局,所以设为无限大
那么我们按深度从大到小排一遍序就可以了,如果当前dis[i]>2,就在祖父节点那里设立消防局
至于dis[i],可以一边做一边更新
Code
#include<bits/stdc++.h>
#define in(i) (i=read())
#define rg register
#define il extern inline
using namespace std;
const int N=1e3+10;
int read() {
int ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=ans*10+(i^48),i=getchar();
return ans*f;
}
int n,ans;
int dep[N],dis[N],id[N],f[N];
bool cmp(int a,int b) {return dep[a]>dep[b];}
int main()
{
in(n); id[1]=1,dis[1]=dis[0]=N;
for(rg int i=2;i<=n;i++) {
in(f[i]); dep[i]=dep[f[i]]+1;//保证f[i]<i
id[i]=i,dis[i]=N;
}
sort(id+1,id+1+n,cmp);
for(rg int i=1;i<=n;i++) {
int u=id[i],v=f[u],gf=f[v];
dis[u]=min(dis[u],min(dis[v]+1,dis[gf]+2));
if(dis[u]>2) {
dis[gf]=0,ans++;
dis[f[gf]]=min(dis[f[gf]],1),dis[f[f[gf]]]=min(dis[f[f[gf]]],2);
}
}
cout<<ans<<endl;
}