Bessie's Function

题目描述

Bessie 有一个特殊函数 $f(x)$，输入为 $[1, N]$ 中的一个整数，并返回 $[1, N]$ 中的一个整数（$1 \le N \le 2 \cdot 10^5$）。她的函数 $f(x)$ 由 $N$ 个整数 $a_1 \ldots a_N$ 定义，其中 $f(x) = a_x$（$1 \le a_i \le N$）。 Bessie 希望这个函数是幂等的。换句话说，它应当对所有整数 $x \in [1, N]$ 满足 $f(f(x)) = f(x)$。 以代价 $c_i$，Bessie 可以将 $a_i$ 的值改为 $[1, N]$ 中的任意整数（$1 \le c_i \le 10^9$）。请确定使 $f(x)$ 变为幂等所需的最小总代价。

输入格式

第一行包含 $N$。 第二行包含 $N$ 个用空格分隔的整数 $a_1,a_2,\dots,a_N$。 第三行包含 $N$ 个用空格分隔的整数 $c_1,c_2,\dots,c_N$。

输出格式

输出使 $f(x)$ 成为幂等所需的最小总代价。

5
2 4 4 5 3
1 1 1 1 1

3

8
1 2 5 5 3 3 4 4
9 9 2 5 9 9 9 9

7

提示

我们可以将 $a_1 = 4$、$a_4 = 4$、$a_5 = 4$。由于所有 $c_i$ 都等于 1，总花费等于 $3$，也就是修改次数。可以证明不存在仅用 $2$ 次或更少修改的解。 我们将 $a_3 = 3$ 且 $a_4 = 4$。总花费为 $2+5=7$。 评分： 子任务： 输入 3：$N\le 20$ 输入 4-9：$a_i\ge i$ 输入 10-15：所有 $a_i$ 互不相同。 输入 16-21：无额外限制。 此外，在最后三个子任务中的每一个子任务里，前一半的测试将满足对所有 $i$ 有 $c_i=1$。 题目鸣谢：Avnith Vijayram

标签: USACO|2025|Gold

来源

USACO|2025|Gold