#P1475. [USACO2.3] 控制公司 Controlling Companies
[USACO2.3] 控制公司 Controlling Companies
题目描述
有些公司是其他公司的部分拥有者,因为他们获得了其他公司发行的股票的一部分。
据说,如果至少满足了以下三个条件之一,公司 就可以控制公司 了:
- 公司 = 公司 。
- 公司 拥有大于 的公司 的股票。
- 公司 控制 ()个公司,记为 ,每个公司 拥有 的公司 的股票,并且 。
给你一个表,每行包括三个数 :表明公司 享有公司 的 的股票。计算所有的数对 ,表明公司 控制公司 。至多有 个公司。
输入格式
第一行一个整数 ,表明表格的行数。
接下来 行,每行三个整数 ,表示 公司拥有 公司 的股份。
输出格式
输出零个或更多个的控制其他公司的公司。每行包括两个整数 ,表示 公司控制了 公司。将输出的数对以 为第一关键字, 为第二关键字升序排列。
请不要输出控制自己的公司(即你输出的数对均要满足 )。
3
1 2 80
2 3 80
3 1 20
1 2
1 3
2 3
提示
翻译来自NOCOW
USACO 2.3