#P7221. [JSOI2010] 蔬菜庆典

[JSOI2010] 蔬菜庆典

题目描述

JYY 在火星上找到一片埋有宝藏的岛,并且带走了一些宝藏。之后 JYY 被火星人发现偷宝藏,抓了起来。火星人打算吃掉 JYY,除非 JYY 能在火星年度蔬菜庆典的游戏中赢得足够多的火星币来支付他带走宝藏的费用。

游戏在蔬菜广场上进行。首先放进广场的是一个巨大的转基因南瓜,接着各种其他巨大的蔬菜被陆续拖进广场,连同大南瓜一共 nn 个,第 ii 个放入的蔬菜会用一根绳子和先前放入的某个蔬菜连接起来。按照火星人的说法,蔬菜 ii 是蔬菜 pip_i 的 Dlihc,蔬菜 pip_i 是蔬菜 ii 的 Tnerap。JYY 立即看出,一开始的大南瓜没有 Tnerap,后来的每个蔬菜都恰好有一个 Tnerap;每个蔬菜可能有一个或多个的 Dlihc,也可能没有。nn 个蔬菜全部在广场上安置好后,火星人在每个蔬菜上贴一张纸条,蔬菜 ii 的纸条上写着一个整数 viv_i,表示这个蔬菜的价钱。

游戏一个接一个地进行着。在整个晚会将要结束时,JYY 终于等到了适合自己的那一个。(你不能指望有恐高症的 JYY 会在蔬菜间玩走钢丝,尽管那样能有丰厚的报酬)。游戏规则是:游戏者(也就是 JYY)每次可以选择任意一个既有 Dlihc 又有 Tnerap 的蔬菜 ii,将它的价钱 viv_i 改成 vp+vcviv_p+v_c-v_i,其中 pp 代表蔬菜 ii 的 Tnerap 的编号,cc 代表蔬菜 ii 的任意一个 Dlihc 的编号。火星人给的时间比较宽裕,足够 JYY 进行任意多次操作。当 JYY 决定不再操作时,游戏结束。之后所有巨型蔬菜将被火星政府按蔬菜上的标价收购。买菜所得的钱归 JYY 所有,用以支付他的债务。

JYY 想知道,他最多能把这些蔬菜卖出多少钱,或者他能通过一系列操作使得蔬菜的总价无限制地增大。请你帮助 JYY 解决这个问题。

输入格式

输入文件有多组数据,每组数据的格式为:

第一行一个整数 nn 表示广场上蔬菜的个数。

接下来 nn 行,每行两个整数 pi,vip_i,v_i,第 ii 行中的整数代表蔬菜 ii 的 Tnerap 的编号和蔬菜 ii 的价格。

n=0n=0 时表示输入结束。

输出格式

对于每组数据,输出一行。若蔬菜的总价能无限制增大,输出 +inf。否则输出一个整数,表示所有蔬菜的最大总价。

5
-1 3
1 2
1 1
3 2
3 2
5
-1 3
1 2
1 1
3 2
3 3
0
13
+inf

提示

样例解释 1

共有两组数据。

对于第一组数据,我们只能对蔬菜 33 进行操作,它的值只能是 1144,所以答案为 3+2+4+2+2=133+2+4+2+2=13

对于第二组数据,可以按照如下方法使得所有蔬菜的价钱无限制地增大:

$$\begin{matrix}1\to 3+3-1=5\\5\to 3+2-5=0\\0\to 3+3-0=6\\6\to 3+2-6=-1\\-1\to 3+3-(-1)=7\\\cdots\end{matrix} $$

数据范围

对于 100%100\% 的数据,n2×105,107vi107n\leq 2\times 10^5,-10^7\leq v_i\leq 10^7