P6892: 访问

---

【题目描述】

【题目描述】
Bessie 的 N（2≤N≤10^5）个奶牛伙伴（编号为 1…N）每一个都拥有自己的农场。对于每个 1≤i≤N，伙伴 i想要访问伙伴 ai（ai≠i）。
给定 1…N 的一个排列 (p1,p2,…,pN)，访问按以下方式发生。
对于 1 到 N 的每一个 i：
l 如果伙伴 api 已经离开了她的农场，则伙伴 pi 仍然留在她的农场。
l 否则，伙伴 pi 离开她的农场去访问伙伴 api 的农场。这次访问会产生快乐的哞叫 vpi 次（0≤vpi≤10^9）。
对于所有可能的排列 p，计算所有访问结束后可能得到的最大哞叫次数。
【输入格式】（从终端 / 标准输入读入）：
输入的第一行包含 NN。
对于每一个 1≤i≤N，第 i+1 行包含两个空格分隔的整数 ai 和 vi。
【输出格式】（输出至终端 / 标准输出）：
输出一个整数，为所求的答案。
注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 "long long"）。
【输入样例】：
4
2 10
3 20
4 30
1 40
【输出样例】：
90
【样例说明】
如果 p=(1,4,3,2)，则
l 伙伴 1 访问伙伴 2 的农场，产生 10 次哞叫。
l 伙伴 4 看到伙伴 1 已经离开了农场，所以无事发生。
l 伙伴 3 访问伙伴 4 的农场，又产生 30 次哞叫。
l 伙伴 2 看到伙伴 3 已经离开了农场，所以无事发生。
这样总计得到了 10+30=40 次哞叫。
另一方面，如果 p=(2,3,4,1)，则
l 伙伴 2 访问伙伴 3 的农场，产生 20 次哞叫。
l 伙伴3 访问伙伴 4 的农场，产生 30 次哞叫。
l 伙伴 4 访问伙伴 1 的农场，产生 40 次哞叫。
l 伙伴 1 看到伙伴 2 已经离开了农场，所以无事发生。
这样总计得到了 20+30+40=90 次哞叫。可以证明这是所有可能的排列 p 中访问结束后得到的最大可能的哞叫次数。
【测试点性质】：
测试点 2-3 对于所有的 i≠j 满足 ai≠aj。
测试点 4-7 满足 N≤10^3。
测试点 8-11 没有额外限制。
 

题目类型~

USACO-2022-银-公开赛 

咻咻~

提交答案 状态 返回