[USACO2.3] 控制公司 Controlling Companies

题目描述

有些公司是其他公司的部分拥有者,因为他们获得了其他公司发行的股票的一部分。 据说,如果至少满足了以下三个条件之一,公司 $A$ 就可以控制公司 $B$ 了: - 公司 $A$ = 公司 $B$。 - 公司 $A$ 拥有大于 $50\%$ 的公司 $B$ 的股票。 - 公司 $A$ 控制 $K$($K \geq 1$)个公司,记为 $C_1, \ldots, C_K$,每个公司 $C_i$ 拥有 $x_i\%$ 的公司 $B$ 的股票,并且 $x_1+ \ldots + x_K \gt 50\%$。 给你一个表,每行包括三个数 $i,j,p$:表明公司 $i$ 享有公司 $j$ 的 $p\%$ 的股票。计算所有的数对 $(h,s)$,表明公司 $h$ 控制公司 $s$。至多有 $100$ 个公司。

输入输出格式

输入格式


第一行一个整数 $N$,表明表格的行数。 接下来 $N$ 行,每行三个整数 $i,j,p$,表示 $i$ 公司拥有 $j$ 公司 $p\%$ 的股份。

输出格式


输出零个或更多个的控制其他公司的公司。每行包括两个整数 $A,B$,表示 $A$ 公司控制了 $B$ 公司。将输出的数对以 $A$ 为第一关键字,$B$ 为第二关键字升序排列。 请不要输出控制自己的公司(即你输出的数对均要满足 $A \neq B$)。

输入输出样例

输入样例 #1

3
1 2 80
2 3 80
3 1 20

输出样例 #1

1 2
1 3
2 3

说明

翻译来自NOCOW USACO 2.3