首页 > > 程序设计 > C/C++ >

P2279 [HNOI2003]消防局的设立

2018-06-17 22:29:50来源：未知阅读 ()

题目描述

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：

输出样例#1：

2

这是一道非常好的贪心+dfs+图论的题目
首先我们先以1为根节点建一棵数
然后我们可以推出，如果想要找到最小的答案，那么我们可以从树根开始建消防站
那么就简单了，
dfs建树，找两次祖先
然后dfs处理边

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 using namespace std;
  8 const int MAXN=1001;
  9 int n,tot=0,ans=0;
 10 struct linjiebiao
 11 {
 12     int u;
 13     int v;
 14     int nxt;
 15 }edge[MAXN*4];
 16 int head[MAXN];
 17 int num=1;
 18 int vis[MAXN];
 19 int deep[MAXN];
 20 int read(int & n)
 21 {
 22     int flag=0,x=0;char c='/';
 23     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 24     while(c>='0'&&c<='9')x=x*10+(c-48),c=getchar();
 25     if(flag)n=-x;else n=x;
 26 }
 27 void add_edge(int ll,int rr)
 28 {
 29     edge[num].u=ll;
 30     edge[num].v=rr;
 31     edge[num].nxt=head[ll];
 32     head[ll]=num++;
 33 }
 34 void makedeep()
 35 {
 36     deep[1]=1;
 37     queue<int>q;
 38     q.push(1);
 39     while(q.size()!=0)
 40     {
 41         int p=q.front();
 42         q.pop();
 43         for(int i=head[p];i!=-1;i=edge[i].nxt)
 44         {
 45             int to=edge[i].v;
 46             if(deep[to]==0)
 47             {
 48                 deep[to]=deep[p]+1;
 49                 q.push(to);
 50             }
 51         }
 52     }
 53 }
 54 void dele(int where,int cs)
 55 {
 56     if(vis[where]==0)
 57         tot++;
 58     vis[where]=1;
 59     if(cs==3)
 60     return ;
 61     for(int i=head[where];i!=-1;i=edge[i].nxt)
 62     {
 63         dele(edge[i].v,cs+1);
 64     }
 65 }
 66 int main()
 67 {
 68     read(n);
 69     for(int i=1;i<=n;i++)
 70     head[i]=-1;
 71     for(int i=2;i<=n;i++)
 72     {
 73         int p;
 74         read(p);
 75         add_edge(i,p);
 76         add_edge(p,i);
 77     }
 78     
 79     makedeep();
 80     
 81     while(tot<n)
 82     {
 83         ans++;
 84         int now=0;
 85         for(int i=1;i<=n;i++)
 86             if(deep[i]>deep[now]&&!vis[i])
 87                 now=i;
 88                 
 89         for(int i=head[now];i!=-1;i=edge[i].nxt)
 90         {
 91             if(deep[edge[i].v]<deep[now])
 92             {
 93                 now=edge[i].v;
 94                 break;
 95             }
 96         }
 97         for(int i=head[now];i!=-1;i=edge[i].nxt)
 98         {
 99             if(deep[edge[i].v]<deep[now])
100             {
101                 now=edge[i].v;
102                 break;
103             }
104         }
105         dele(now,1);
106     }
107     
108     printf("%d",ans);
109     
110     return 0;
111 }