P2279[HNOI2003]消防局的设立
Vimin
·
·
个人记录
题目传送P2279
题意
- 一个点管辖的距离是二
- 与P2458保安站岗不同,它是管辖距离为1。这道题距离变成2,没有点权
- 管辖距离为1 设3种状态,管辖距离为2则要设更多
- 所以我们因为太麻烦,换贪心。因为毕竟没有点权
- 每次考虑深度最深的点,管辖它可以设它,设父亲,设父亲的父亲,设兄弟。结果发现,设父亲的父亲的话会把这些点都管辖到。设父亲一定是最优的
- 所以我们每次找到深度最深的一个点在它的父亲的父亲的设点。
- 可以用大根堆实现
- 比较函数没写return 调了1个多小时
代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n,tot,ans;
bool vis[1505];
int head[1505];
int dep[1505],fa[1505];
struct node{
int to,net;
}e[3005];
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){
e[++tot].to =y,e[tot].net=head[x],head[x]=tot;
e[++tot].to =x,e[tot].net=head[y],head[y]=tot;
}
void dfs1(int x,int f,int depth){
fa[x]=f;
dep[x]=depth;
for(int i=head[x];i;i=e[i].net ){
int to=e[i].to ;
if(to==f) continue;
dfs1(to,x,depth+1);
}
}
void dfs2(int x,int depth){
if(depth>2) return ;
vis[x]=1;
for(int i=head[x];i;i=e[i].net )
dfs2(e[i].to ,depth+1);
}
int main()
{
scanf("%d",&n);
for(int i=2;i<=n;i++){
int x;
scanf("%d",&x);
add(i,x);
}
dfs1(1,0,1);
// for(int i=1;i<=n;i++) printf("%d %d\n",fa[i],dep[i]);
// cout<<endl;
for(int i=1;i<=n;i++) q.push(i);
int x;
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",ans);
return 0;
}