自动搬运

查看原文

来自洛谷，原作者为

	WRuperD forget#2501

搬运于2025-08-24 22:32:52，当前版本为作者最后更新于2022-07-18 07:57:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

40pts

由题意我们可以发现，对于每个城市我们只有两种选择，改变或不改变，爆搜即可。

100pts

既然只有两种状态，且操作的先后顺序不影响结果，我们有端联想到 P1391 和 P1764.我们发现，对于第 $i$ 个城市，如果我们确定了它的状态，剩下的 $n-1$ 个城市可以通过贪心求解出它们的答案。首先我们需要用 01 串来表示第 $i$ 个城市与其他城市的相连状态。 我们假设：

第一个城市: 0 1 0

第二个城市: 1 0 0

第三个城市: 0 0 0

我们假设对第一个城市进行一次操作后变为：

第一个城市: 1 0 1

第二个城市: 0 0 0

第三个城市: 1 0 0

对于第二个城市，它与第一个，第三个城市均不相连，我们不如给他操作一次才有可能游街。

即：对于第 $i$ 个城市，如果它与第 $j$ 个城市不相连，操作它一次。

最后，我们只需要对于第一个城市操作和不操作分别贪心一次即可获得答案。