P2279 [HNOI2003]消防局的设立

6
1
2
3
4
5

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 }