题解 P2279 【[HNOI2003]消防局的设立】

· · 题解

这题贪心比较好想

考虑当前深度最大的叶子结点，你肯定要有一个消防局去覆盖它，

那么既然他是叶子结点，所以与他距离小于等于2的节点有这么几种：

  1. 他的父亲 2. 他的兄弟 3. 他的爷爷

容易看出，在前两项能够覆盖到的节点，在爷爷那里设立一定也能覆盖到。

所以每次贪心取出深度最大的节点，在他的爷爷哪里放一个消防站

用STL的priority_queue，时间复杂度O(nlogn)

#include<bits/stdc++.h>
#define maxn 1010
#define maxm 2010
using namespace std;

int head[maxn],point[maxm],nxt[maxm],dep[maxn],fa[maxn],tot=0;
bool vis[maxn];
struct cmp{
    bool operator () (int &a,int &b){
        return dep[a]<dep[b];
    } 
};
priority_queue<int,vector<int>,cmp> q;
void add(int x,int y){
    point[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
void dfs(int temp,int father,int depth){
    fa[temp]=father;
    dep[temp]=depth;
    for(int j=head[temp];j;j=nxt[j]){
        if(point[j]==father)
            continue;
        dfs(point[j],temp,depth+1);
    }
}
void dfs2(int temp,int depth){
    if(depth>2)
        return;
    vis[temp]=true;
    for(int j=head[temp];j;j=nxt[j])
        dfs2(point[j],depth+1);
}
int main(){
    int n,cnt,x,y,ans=0;
    scanf("%d",&n),cnt=n;
    for(int i=1;i<=n-1;i++)
        scanf("%d",&x),add(i+1,x),add(x,i+1);
    dfs(1,0,1);
    for(int i=1;i<=n;i++)
        q.push(i);
    while(q.size()){
        while(q.size()&&vis[x=q.top()])
            q.pop();
        if(!q.size())
            break;
        if(fa[fa[x]])
            dfs2(fa[fa[x]],0);
        else
            dfs2(1,0);
        ans++; 
    }
    printf("%d\n",ans);
    return 0;
}