#P1475. [USACO2.3] 控制公司 Controlling Companies

[USACO2.3] 控制公司 Controlling Companies

题目描述

有些公司是其他公司的部分拥有者,因为他们获得了其他公司发行的股票的一部分。

据说,如果至少满足了以下三个条件之一,公司 AA 就可以控制公司 BB 了:

  • 公司 AA = 公司 BB
  • 公司 AA 拥有大于 50%50\% 的公司 BB 的股票。
  • 公司 AA 控制 KKK1K \geq 1)个公司,记为 C1,,CKC_1, \ldots, C_K,每个公司 CiC_i 拥有 xi%x_i\% 的公司 BB 的股票,并且 x1++xK>50%x_1+ \ldots + x_K \gt 50\%

给你一个表,每行包括三个数 i,j,pi,j,p:表明公司 ii 享有公司 jjp%p\% 的股票。计算所有的数对 (h,s)(h,s),表明公司 hh 控制公司 ss。至多有 100100 个公司。

输入格式

第一行一个整数 NN,表明表格的行数。

接下来 NN 行,每行三个整数 i,j,pi,j,p,表示 ii 公司拥有 jj 公司 p%p\% 的股份。

输出格式

输出零个或更多个的控制其他公司的公司。每行包括两个整数 A,BA,B,表示 AA 公司控制了 BB 公司。将输出的数对以 AA 为第一关键字,BB 为第二关键字升序排列。

请不要输出控制自己的公司(即你输出的数对均要满足 ABA \neq B)。

3
1 2 80
2 3 80
3 1 20
1 2
1 3
2 3

提示

翻译来自NOCOW

USACO 2.3