首页 > 其他 > 详细

HNOI2003 消防局的设立

时间:2019-11-14 10:51:15      阅读:88      评论:0      收藏:0      [点我收藏+]

题目传送门

据说是一道树形DP,这么高级的么……
然而贪心就可以


因为消防局可以扑灭与它距离不超过2的基地的火灾,所以我们可以每次找出深度最大的点(用堆维护),然后在他的爷爷节点(没有爷爷就在父亲节点)建一个消防局

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int read(){
    int k=0; char c=getchar();
    for(;c<'0'||c>'9';) c=getchar();
    for(;c>='0'&&c<='9';c=getchar())
      k=k*10+c-48;
    return k;
}
struct zzz{
    int t,nex;
}e[1010<<1]; int head[1010],tot;
void add(int x,int y){
    e[++tot].t=y;
    e[tot].nex=head[x];
    head[x]=tot;
}
int fa[1010],vis[1010],deth[1010],ans;
void dfs(int now){
    for(int i=head[now];i;i=e[i].nex)
      if(e[i].t!=fa[now]){
          fa[e[i].t]=now; deth[e[i].t]=deth[now]+1;
          dfs(e[i].t);
      }
}
struct hhh{
    int k,deth;
    bool operator < (const hhh &y) const{
        return deth < y.deth;
    }
};
priority_queue <hhh> q;
int main(){
    int n=read();
    for(int i=2;i<=n;i++){
        int x=read(); add(i,x); add(x,i);
    }
    dfs(1);
    for(int i=1;i<=n;i++) q.push(hhh{i,deth[i]});
    while(!q.empty()){
        int k=q.top().k; q.pop();
        if(vis[k]) continue;
        ans++;
        if(fa[fa[k]]){
            vis[fa[fa[k]]]=1;
            for(int i=head[fa[fa[k]]];i;i=e[i].nex){
                vis[e[i].t]=1;
                for(int j=head[e[i].t];j;j=e[j].nex) vis[e[j].t]=1;
            }
        }
        else{
            vis[fa[k]]=1;
            for(int i=head[fa[k]];i;i=e[i].nex) vis[e[i].t]=1;
        }
    }
    cout<<ans;
    return 0;
}

HNOI2003 消防局的设立

原文:https://www.cnblogs.com/morslin/p/11854821.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!