526互联

[AGC004D] Teleporter 题解

发布时间 2023-08-18 20:06:39作者: Al_lA

简单贪心。

思路

可以发现一号节点必然连向自己。

由于题目中保证了最初每个点都可以到达一号节点。

那么我们发现改完一后，原图变成了一棵十分优美的树。

考虑在树上进行贪心。

我们贪心的从叶子结点往上走。

知道第 \(k\) 个若还没要到 \(1\)，就直接连向一号节点。

这个贪心也比较容易理解。

实现也很简单。

Code

AC记录。