2022 Usaco US Open银组题解，有哪些解题技巧分享？

本文共计2855个文字，预计阅读时间需要12分钟。

T1+题目简述+有+（n）+只奶牛，第+（i）+只奶牛希望拜访第+（a_i）+只奶牛。给定一个+（1）+到+（N）+的排列+（（p_1，p_2，...，p_n）+），对于从+（1）+到+（n）+的每一个+（i）+：如果奶牛+（a_{p_i}）+已经访问过。

T1

题意简述

• 有 \(n\) 只奶牛，第 \(i\) 只奶牛希望拜访第 \(a_i\) 只奶牛。
• 给定一个 \(1\) . . . \(N\) 的排列 \((p_1, p_2, ..., p_n)\)，对于从 \(1\) 到 \(n\) 的每一个 \(i\)：
  • 如果奶牛 \(a_{p_i}\) 已经离开了她的农场，那么奶牛 \(p_i\) 仍然留在她的农场。
  • 否则，奶牛 \(p_i\) 就会离开她的农场去拜访第 \(a_{p_i}\) 只奶牛，并产生 \(v_{p_i}\) 次快乐的哞叫。
• 给出序列 \(a_n\) 与 \(v_n\)，对于所有可能的排列 \(p\)，计算可能得到的快乐哞叫的次数的最大值。
• \(2 \leq n \leq 10^5\)，\(0 \leq v_i \leq 10^9\)。

解题思路

十分有趣的图论题。

我们建立一个 \(n\) 条边 \(n\) 个点的有向图，第 \(i\) 条边从 \(i\) 连向 \(a_i\)。注意到图不一定连通。

首先考虑对于 \(a_i \neq a_j\) 的部分分如何解决。这种情况下，每个连通块都形成一个简简单单的环。