题解 P2279 【[HNOI2003]消防局的设立】
George1123
·
·
题解
{\color{orange}\text{欢迎拜访我这个蒟蒻的博客}}
此题的算法标签为：贪心、dfs，但我只用贪心就过了(用dp也可以）
思路
因为图中有n个点和n-1条边，所以这是一棵树，处理时处理单个节点就行了。
贪心思路：找最深的节点并在其祖父节点上建造消防局：
1.构造树的节点i
因为树节点要按深度d排序，所以要记录树节点的原编号s，以便查询其父亲节点f[i]、覆盖程度p[i]。
struct node{
int d,s;
}a[1010];
int n,ans,f[1010],p[1010];
{\color{red}\text{如果把\textit{f}、\textit{p}包装进结构体\textit{node}}}$，${\color{red}\text{父亲节点所对应的值便无法查询}}
2.读入处理并排序
f[i]$只有$n-1$个，第一个节点的$s$要置成$1
bool cmp(node x,node y){
return x.d>y.d;
} int main(){
scanf("%d",&n);
a[1].s=1;
for(int i=2;i<=n;i++){
scanf("%d",f+i);
a[i].d=a[f[i]].d+1;
a[i].s=i;
} sort(a+1,a+n+1,cmp);
3.按照思路，建造消防局
不用dfs，不用树遍历：
3：消防局覆盖度；
2：消防局儿子父亲节点；
1：消防局孙子祖父节点；
0：消防局无法覆盖节点。
```cpp
for(int i=1;i<=n;i++){
//(1)继承祖先节点覆盖
p[a[i].s]=max(p[a[i].s],
max(p[f[a[i].s]]-1,
p[f[f[a[i].s]]]-2));
//(2)如果当前节点未被覆盖，在其祖父节点上建造消防局
if(!p[a[i].s]){
ans++;
//①覆盖祖父节点
p[f[f[a[i].s]]]=3;
//②覆盖父亲、当前节点
p[f[a[i].s]]=2;
p[a[i].s]=1;
//③覆盖曾祖父、玄祖父
p[f[f[f[a[i].s]]]]=
max(p[f[f[f[a[i].s]]]],2);
p[f[f[f[f[a[i].s]]]]]=
max(p[f[f[f[f[a[i].s]]]]],1);
}
}
```
然后这里的$ans$就是答案了。
## 以下是完整代码
```cpp
#include <bits/stdc++.h>
using namespace std;
struct node{
int d,s;
}a[1010];
int n,ans,f[1010],p[1010];
bool cmp(node x,node y){
return x.d>y.d;
} int main(){
scanf("%d",&n);
a[1].s=1;
for(int i=2;i<=n;i++){
scanf("%d",f+i);
a[i].d=a[f[i]].d+1;
a[i].s=i;
} sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
p[a[i].s]=max(p[a[i].s],
max(p[f[a[i].s]]-1,
p[f[f[a[i].s]]]-2));
if(!p[a[i].s]){
ans++;
p[f[f[a[i].s]]]=3;
p[f[a[i].s]]=2;
p[a[i].s]=1;
p[f[f[f[a[i].s]]]]=
max(p[f[f[f[a[i].s]]]],2);
p[f[f[f[f[a[i].s]]]]]=
max(p[f[f[f[f[a[i].s]]]]],1);
}
} printf("%d\n",ans);
return 0;
}
```
谢谢观看此题解的巨佬观众们！