NC20031. [HNOI2003]消防局的设立
描述
输入描述
输入文件的第一行为n，表示火星上基地的数目。
接下来的n-1行每行有一个正整数，其中文件第i行的正整数为a[i]，表示从编号为i的基地到编号为a[i]的基地之间有一条道路，为了更加简洁的描述树状结构的基地群，有a[i]
输出描述
输出文件仅有一个正整数，表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的火灾。
示例1
输入:
6 1 2 3 4 5
输出:
2
C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 396K, 提交时间: 2022-09-02 23:29:24
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=1e5+100;
int f[N],a[N],o[N],d[N];
bool cmp(int x,int y)
{
return d[x]>d[y];
}
int main()
{
int n;
cin>>n;
a[1]=1;o[1]=N;o[0]=N;
for(int i=2;i<=n;i++)
{
cin>>f[i];
d[i]=d[f[i]]+1;
a[i]=i;o[i]=N;
}
sort(a+1,a+1+n,cmp);
int ans=0;
for(int i=1;i<=n;i++)
{
int x=a[i],v=f[x],u=f[f[x]];
o[x]=min(o[x],min(o[v]+1,o[u]+2));
if(o[x]>2)
{
o[u]=0;
ans++;
o[f[u]]=min(o[f[u]],1);
o[f[f[u]]]=min(o[f[f[u]]],2);
}
}
cout<<ans<<endl;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 496K, 提交时间: 2020-03-27 20:22:26
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int f[N],a[N],o[N],d[N];
bool cmp(int x,int y)
{
return d[x]>d[y];
}
int main()
{
int n;
cin>>n;
a[1]=1;o[1]=N;o[0]=N;
for(int i=2;i<=n;i++)
{
cin>>f[i];
d[i]=d[f[i]]+1;
a[i]=i;o[i]=N;
}
sort(a+1,a+1+n,cmp);
int ans=0;
for(int i=1;i<=n;i++)
{
int x=a[i],v=f[x],u=f[f[x]];
o[x]=min(o[x],min(o[v]+1,o[u]+2));
if(o[x]>2)
{
o[u]=0;
ans++;
o[f[u]]=min(o[f[u]],1);
o[f[f[u]]]=min(o[f[f[u]]],2);
}
}
cout<<ans<<endl;
return 0;
}