Visits

题目描述

贝茜的 $N$ 个（$2\le N\le 10^5$）牛伙伴（方便起见编号为 $1\ldots N$）每个都有自己的农场。对于每个 $1\le i\le N$，伙伴 $i$ 想去拜访伙伴 $a_i$（$a_i\neq i$）。 给定一个由 $1\ldots N$ 组成的排列 $(p_1,p_2,\ldots, p_N)$，拜访按如下方式进行。 对于每个 $i$ 从 $1$ 到 $N$： 如果伙伴 $a_{p_i}$ 已经离开了她的农场，那么伙伴 $p_i$ 留在自己的农场不动。 否则，伙伴 $p_i$ 离开自己的农场去拜访伙伴 $a_{p_i}$ 的农场。 这次拜访会带来愉快的“哞”声，被喊出 $v_{p_i}$ 次（$0\le v_{p_i}\le 10^9$）。 请在所有可能的排列 $p$ 中，计算所有拜访结束后“哞”声次数的最大可能总数。

输入格式

第一行包含 $N$。 对于每个 $1\le i\le N$，第 $i+1$ 行包含两个用空格分隔的整数 $a_i$ 和 $v_i$。

输出格式

输出一个整数表示答案。 注意：本题涉及的整数可能很大，可能需要使用 64 位整数类型（例如 C/C++ 中的 "long long"）。

4
2 10
3 20
4 30
1 40

90

提示

如果 $p=(1,4,3,2)$，则 伙伴 $1$ 访问伙伴 $2$ 的农场，产生 $10$ 次哞声。 伙伴 $4$ 发现伙伴 $1$ 已经离开，因此什么也不会发生。 伙伴 $3$ 访问伙伴 $4$ 的农场，增加 $30$ 次哞声。 伙伴 $2$ 发现伙伴 $3$ 已经离开，因此什么也不会发生。 总计得到 $10+30=40$ 次哞声。 另一方面，如果 $p=(2,3,4,1)$，则 伙伴 $2$ 访问伙伴 $3$ 的农场，产生 $20$ 次哞声。 伙伴 $3$ 访问伙伴 $4$ 的农场，产生 $30$ 次哞声。 伙伴 $4$ 访问伙伴 $1$ 的农场，产生 $40$ 次哞声。 伙伴 $1$ 发现伙伴 $2$ 已经离开，因此什么也不会发生。 总计得到 $20+30+40=90$ 次哞声。可以证明，在所有排列 $p$ 中，这就是所有拜访结束后可能得到的最大哞声总数。 SCORING: 测试点 2-3 满足对所有 $i\neq j$ 都有 $a_i\neq a_j$。 测试点 4-7 满足 $N\le 10^3$。 测试点 8-11 没有额外限制。 题目鸣谢：Benjamin Qi 和 Michael Cao

标签: USACO|2022|Silver

来源

USACO|2022|Silver