1217. [HNOI2003]消防局的设立【贪心】

Description

2020年，人类在火星上建立了一个庞大的基地群，总共有n个基地。起初为了节约材料，人类只修建了n-1条道路来

连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地A到

基地B至少要经过d条道路的话，我们称基地A到基地B的距离为d。由于火星上非常干燥，经常引发火灾，人类决定

在火星上修建若干个消防局。消防局只能修建在基地里，每个消防局有能力扑灭与它距离不超过2的基地的火灾。

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

。

Input

第一行为n，表示火星上基地的数目。N<=1000

接下来的n-1行每行有一个正整数，其中文件第i行的正整数为a[i]，表示从编号为i的基地到编号为a[i]的基地之间有一条道路，

为了更加简洁的描述树状结构的基地群，有a[i] < i

Output

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

Sample Input

6
1
2
3
4
5

Sample Output

2

这果然是个sb贪心……
我们每次找一个最深的节点，然后在这个节点的爷爷上建一个消防站
因为深度最深的这个点必然要被覆盖
而能覆盖到最深的点只有在该点的爷爷修建才是最优方案
然后我们就O(N^2)每次找一个最深的
然后贪心就好了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 using namespace std;
 6 
 7 int head[1010],num_edge;
 8 int n,Father[1010],Depth[1010];
 9 bool used[1010];
10 struct node
11 {
12     int to,next;
13 }edge[2010];
14 
15 void add(int u,int v)
16 {
17     edge[++num_edge].to=v;
18     edge[num_edge].next=head[u];
19     head[u]=num_edge;
20 }
21 
22 void Build(int x)
23 {
24     Depth[x]=Depth[Father[x]]+1;
25     for (int i=head[x];i!=0;i=edge[i].next)
26         if (edge[i].to!=Father[x])
27         {
28             Father[edge[i].to]=x;
29             Build(edge[i].to);
30         }
31 }
32 
33 int main()
34 {
35     int x;
36     scanf("%d",&n);
37     for (int i=2;i<=n;++i)
38     {
39         scanf("%d",&x);
40         add(x,i);
41         add(i,x);
42     }
43     Build(1);
44     int ans=0;
45     while (1)
46     {
47         int x=0;
48         bool flag=false;
49         for (int i=1;i<=n;++i)
50             if (!used[i] && Depth[i]>Depth[x])
51                 x=i,flag=true;
52         if (!flag)
53         {
54             printf("%d",ans);
55             return 0;
56         }
57         x=Father[Father[x]];
58         used[x]=true;
59         used[Father[x]]=used[Father[Father[x]]]=true;
60         for (int i=1;i<=n;++i)
61             if (Father[i]==Father[x] || Father[i]==x || Father[Father[i]]==x)
62                 used[i]=true;
63         ++ans;
64     }
65 }