3810. [USACO Open22 Silver]Visits

【题目描述】

$Bessie$ 的 $N（2≤N≤10^5）$ 个奶牛伙伴（编号为 $1…N$）每一个都拥有自己的农场。对于每个 $1≤i≤N$，伙伴 $i$ 想要访问伙伴 $a_i（ai≠i）$。

给定 $1…N$ 的一个排列 $(p1,p2,…,pN)$，访问按以下方式发生。

对于 $1$ 到 $N$ 的每一个 $i$：

• 如果伙伴 $a_{p_i}$ 已经离开了她的农场，则伙伴 $p_i$ 仍然留在她的农场。


• 否则，伙伴 $p_i$ 离开她的农场去访问伙伴 $a_{p_i}$ 的农场。这次访问会产生快乐的哞叫 $v_{p_i}$ 次($0≤v_{p_i}≤10^9$）。

对于所有可能的排列 $p$，计算所有访问结束后可能得到的最大哞叫次数。

【输入格式】

输入的第一行包含 $N$。

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

【输出格式】

输出一个整数，为所求的答案。

注意这个问题涉及到的整数可能需要使用 $64$ 位整数型（例如，$C/C++$ 中的 "$long$ $long$"）。

【样例1输入】

4
2 10
3 20
4 30
1 40

【样例1输出】

90

【样例1说明】

如果 $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$ 中访问结束后得到的最大可能的哞叫次数。

【样例2输入输出】

点击下载样例2 

【数据规模与约定】

测试点 $2-3$ 对于所有的 $i≠j$ 满足 $a_i≠a_j$。

测试点 $4-7$ 满足 $N≤10^3$。

测试点 $8-11$ 没有额外限制。