[AGC004D] Teleporter（贪心+）

Description

维尼管辖的领土很大，我们可以抽象为n个城市，其中1号点为首都。这n个城市之有n条单向电缆，一条信息经过一条电缆进行传输所需时间会+1s，然而维尼并不能忍受时间白白被续，他要求从任何点发出的信息经过恰好ks后恰好出现在首都。

由于时间紧迫，维尼希望修改的电缆数量尽可能地少，他把这个任务交给了你。

Input

第一行两个整数n,k如题目所述

第二行n个正整数，其中第i个正整数a[i]表示有一条从i出发至a[i]的电缆。

题目保证在不做修改的情况下从任一点一定可以走到首都

Output

一行，一个整数，为修改的电缆条数

题解：

严重吐槽本题翻译

这是一道挺有趣的题……

他要让任一点都在 \(K\) 秒到首都，那首都肯定要自环，可以一直转 \(K\) 秒。

那么剩下只有 \(n-1\) 条边了，变成了一颗很漂亮的树。

那我们选一些电缆，把它换成连向1，也就是把原树分成几棵树，其中这几棵树的最大深度不能超过 \(K-1\)。（显然吧，如果距离短了可以在首都的自环上绕）

然后这就可以贪心了！……

CODE：

#include<iostream>

#include<cstdio>

using namespace std;

int n,k,ans=0;

int tot=0,h[100005],a[100005];

struct Edge{

	int x,next;

}e[200005];

inline void add_edge(int x,int y){

	e[++tot].x=y;

	e[tot].next=h[x],h[x]=tot;

}

int dfs(int x,int deep){

	int ret=deep;

	for(int i=h[x];i;i=e[i].next)

		ret=max(ret,dfs(e[i].x,deep+1));

	if(a[x]!=1&&ret-deep==k-1)return ans++,0;

	else return ret;

}

int main(){

	scanf("%d%d",&n,&k);

	for(int i=1;i<=n;i++)scanf("%d",a+i);

	if(a[1]!=1)ans=a[1]=1;

	for(int i=2;i<=n;i++)add_edge(a[i],i);

	dfs(1,0),printf("%d",ans);

}

巴特西

[AGC004D] Teleporter（贪心+）

Description

Input

Output

题解：

CODE：

最新文章

热门文章