关键字：贪心。
Link&Limit
时间限制：1000ms 空间限制：131072kb
Description
2020年，人类在火星上建立了一个庞大的基地群，总共有n个基地。起初为了节约材料，人类只修建了n-1条道路来连接这些基地，并且每两个基地都能够通 过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条道路的话，我们称基地A到基地B的距离为d。
由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。消防局只能修建在基地里，每个消防局有能力扑灭与它距离不超过2的基地的火灾。
你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时，消防队有能力及时扑灭火灾。
Input Format
输入的第一行为n ，表示火星上基地的数目。接下来的n-1行每行有一个正整数，其中第i行的正整数为a[i]，表示从编号为i的基地到编号为a[i]的基地之间有一条道路，为了更加简洁的描述树状结构的基地群，有a[i]<i。
Output Format
仅有一个正整数，表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的火灾。
Sample Input #1
6
1
2
3
4
5
Sample Output #1
2
可以使用贪心解决的问题。按深度从深到浅的顺序访问每个节点，假如某个节点i未被覆盖，那么只要选择该节点的祖父节点即可。
简要说明贪心的正确性：由于节点i是未被覆盖的最深的节点（假定i节点深度为d），我们必然要选择一个深度>=d-2的点来覆盖i。在满足以上条件的情况下，深度为d-2的点所覆盖的点要比深度为d-1以及d的点来得多，所以我们选择i的祖父节点。
#include <stdio.h>
#include <string.h>
int n,fa[1000010],ans = 0;
int e[2000010][2],p[1000010];
int q[1000010],head,tail;
short vis[1000010];
int fastIn()
{
int tans = 0;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar()) tans = tans*10+c-'0';
return tans;
}
void adde(int sn,int fn,int id)
{
id = (id-1)<<1;
e[id][0] = fn; e[id][1] = p[sn]; p[sn] = id;
e[++id][0] = sn; e[id][1] = p[fn]; p[fn] = id;
}
void bfs()
{
int i,sn,fn;
head = 1; tail = 2;
q[1] = 1; vis[1] = 1;
while(head<tail)
{
sn = q[head];
for(i=p[sn];i;i=e[i][1])
{
fn = e[i][0];
if(vis[fn]) continue;
fa[fn] = sn;
q[tail++] = fn; vis[fn] = 1;
}
head++;
}
}
void dfs(int sn,int from,int dep)
{
int i;
if(dep>2) return;
vis[sn] = 1;
for(i=p[sn];i;i=e[i][1])
{
if(i == (from^1)) continue;
dfs(e[i][0],i,dep+1);
}
}
int main()
{
int i,x;
n = fastIn();
for(i=2;i<=n;i++)
{
x = fastIn();
adde(x,i,i);
}
bfs();
memset(vis,0,sizeof(vis));
for(i=tail-1;i;i--)
{
if(vis[q[i]]) continue;
dfs(fa[fa[q[i]]]?fa[fa[q[i]]]:1,0,0); ans++;
}
printf("%d",ans);
return 0;
}
评论 (0)
