形式化题目

公司编号 $1 \dots M$（$M \leqslant 100$）。给定若干条持股关系 $(i, j, p)$，表示公司 $i$ 直接持有公司 $j$ 的 $p\%$ 股份；同一条边可以在输入里出现多次，股份要累加。

在编号上定义一个二元关系「控制」$h \to s$，它是满足下列三条规则的最小关系：

1. $h \to h$（自己控制自己）；
2. $h$ 直接持有 $s$ 的股份大于 $50\%$；
3. 存在若干公司 $c_1, \dots, c_k$（$k \geqslant 1$），每个都满足 $h \to c_t$，且它们直接持有 $s$ 的股份之和大于 $50\%$。

要求输出所有 $h \neq s$ 且 $h \to s$ 的数对 $(h, s)$，按第一关键字升序、第二关键字升序排列。空结果不输出任何内容。

正解

思路

朴素做法。 最直接的想法是：先把"直接持股超过 $50\%$"的边建成有向图，再做一次传递闭包（Floyd 或 BFS），认为传递过去的就是控制。这对样例的前半段没问题——$1$ 持股 $2$ 达 $80\%$，$2$ 持股 $3$ 达 $80\%$，于是 $1$ 也确实控制 $3$。

但这个做法漏掉了规则 3 的真正威力：控制权来自股份的加总，而不是来自一条可以直接走的边。看一个反例：

1
2
31 4 30
2 4 30
1 2 60

公司 $1$ 直接持有 $4$ 的 $30\%$，不控股；但 $1$ 控制 $2$（$60\%$），而 $2$ 也持有 $4$ 的 $30\%$，两条合起来是 $60\% > 50\%$，所以按规则 3，$1$ 控制 $4$。此时的 $1 \to 4$ 在"直接持股图"里根本没有边：单看持股边，$1$ 的那条只有 $30$，怎么传递都凑不出 $50$。必须把"谁被控制"这一层信息喂回给股份统计，两个过程是互相纠缠的。

关键观察：把它看成一个不动点。 换个角度，别去区分"直接控制"和"间接控制"，而是让规则 3 自己描述一个闭包。对固定的 $h$，设 $S$ 是当前已知被 $h$ 控制的公司集合，定义一步算子

其中 $\text{own}[c][s]$ 是 $c$ 直接持有 $s$ 的股份百分比（多条边累加后的值，没有边就是 $0$）。规则 1 给出了起点 $h \in S$，规则 2 是 $S = \{h\}$ 时的特例，规则 3 正是"把 $S$ 里所有公司的持股汇总一次"。

这个算子有三个性质，合起来保证了迭代可用：

• 单调：$S \subseteq T \Rightarrow F_h(S) \subseteq F_h(T)$。持股只做加法，多认识一家公司只会让汇总值变大。
• 扩张：$S \subseteq F_h(S)$，因为 $h \in F_h(S)$ 且旧成员靠规则 1 保留。
• $F_h(S) = F_h(S \cup \{\text{新成员}\})$ 可以逐轮吃进去：这正是题目允许的"边连锁边纳股份"——本轮刚控制到的公司，它持有的股份本轮就能计入。

于是从 $S = \{h\}$ 出发反复做 $S \gets F_h(S)$ 直到 $S$ 不再变大，得到的就是最小不动点，恰好等于题面三条规则定义的控制集（题面说的就是这个最小集合，而不是"先传递再汇总"的某个较大算子）。

用上一节的例子走一遍：$S=\{1\}$ 时，$1$ 对 $4$ 只有 $30$，不控股，$F_1(S)=\{1\}$；但 $1$ 对 $2$ 有 $60$，所以 $F_1$ 其实先把 $2$ 拉进来，$S=\{1,2\}$，再汇总得 $30+30=60>50$，$4$ 才被纳入。$2$ 必须先被收进来，$4$ 的股份才有得加，这一步正是闭包迭代在自动完成的事情。

连锁为什么不用管顺序。 有人会担心"先看 $4$ 还是先看 $2$ 会不会给出不同答案"。不会：因为 $F_h$ 单调，从同一起点出发，任何"合法扩展顺序"得到的集合都夹在最小不动点与最大不动点之间；而这里每轮都把 $F_h$ 一次性作用到当前 $S$ 上（不是只吃一条边），所以每轮结束的 $S$ 就是当前信息下唯一确定的集合，迭代必然停在同一个最小不动点上。

样例验证。 样例数据是 1 2 80、2 3 80、3 1 20、共 $3$ 家公司。逐对看：

去掉"控制自己"的对角线，正好输出 1 2、1 3、2 3，与样例一致。

实现要点。

• 公司编号上限是 $100$，但真实数据里出现的最大编号可能更小。代码取输入中出现过的最大编号 $v$ 作为枚举上界即可，答案排序天然由 for h 升序、for s 升序保证。
• 同一条持股边可能给多次，own[i][j] += p 必须累加；不累加会把 $30+30$ 当成 $30$，直接漏掉上面那个反例。
• 判据是严格大于 $50$，不是大于等于：正好 $50\%$ 不算控制。
• 输出没有答案时不打印任何行；有答案时逐行 h s。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 04:15
# update_at: 2026-10-01 04:15

import sys

MAXV = 100     # 公司编号上限：题面保证 i, j, p 都在 1..100
MAJORITY = 50  # 控股线：汇总持股要「大于 50%」才算控制


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    lines: list[tuple[int, int, int]] = []
    for _ in range(next(data)):
        i, j, p = next(data), next(data), next(data)
        lines.append((i, j, p))

    max_id = max((max(i, j) for i, j, _ in lines), default=0)
    v = max(max_id, 1)  # 公司实际编号范围：控制关系与自身控制都在这个范围内

    # own[a][b] = 公司 a 直接持有 b 的股份百分比；没有股份的边留 0，对不等式无影响
    own = [[0] * (v + 1) for _ in range(v + 1)]
    for i, j, p in lines:
        own[i][j] += p  # 题面允许多组 (i, j, p) 描述同一条持股边，必须累加

    ctrl = [[False] * (v + 1) for _ in range(v + 1)]
    for h in range(1, v + 1):
        ctrl[h][h] = True  # 条件一：控制自己

        # 关系会连锁：本轮新控制到的公司，它的股份本轮立刻能纳进来。
        # 所以反复扫描，直到某一轮没有新增，才说明这条链闭包已经取完。
        while True:
            added = False
            for b in range(1, v + 1):
                if ctrl[h][b]:
                    continue
                # 汇总所有受 h 控制的公司所持有的 b 股份（含 h 自己）
                stake = sum(own[c][b] for c in range(1, v + 1) if ctrl[h][c])
                if stake > MAJORITY:
                    ctrl[h][b] = True
                    added = True
            if not added:
                break

    out = [f"{h} {s}" for h in range(1, v + 1) for s in range(1, v + 1) if ctrl[h][s] and h != s]
    sys.stdout.write("\n".join(out) + ("\n" if out else ""))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 09:25
 * update_at: 2026-10-06 09:25
 */
#include <cstdio>

typedef long long ll;

const int MAXN = 105;   // 公司编号上限：题面保证 i, j, p 都在 1..100
const ll MAJORITY = 50; // 控股线：汇总持股要「大于 50%」才算控制

int n;                  // 输入的三对数数量
int v;                  // 实际出现的最大公司编号，枚举上界
ll own[MAXN][MAXN];     // own[a][b] = 公司 a 直接持有 b 的股份百分比（多条边累加）
bool ctrl[MAXN][MAXN];  // ctrl[h][s] = 公司 h 是否控制公司 s

// 对固定的 h，从 {h} 出发反复做不动点迭代，求出 h 控制的全部公司。
// 每一轮把「当前已知被 h 控制的公司」持有的股份汇总一次，超过 50% 就纳入；
// 关系会连锁：本轮新控制到的公司，它的股份下一轮立刻能计入。
void solve_for(int h) {
    ctrl[h][h] = true; // 条件一：控制自己

    while (true) {
        bool added = false; // 本轮是否有新公司被控制
        for (int s = 1; s <= v; s++) {
            if (ctrl[h][s])
                continue;
            // 汇总所有受 h 控制的公司（含 h 自己）持有的 s 的股份
            ll stake = 0;
            for (int c = 1; c <= v; c++)
                if (ctrl[h][c])
                    stake += own[c][s];
            if (stake > MAJORITY) { // 严格大于 50%：正好 50% 不算控制
                ctrl[h][s] = true;
                added = true;
            }
        }
        if (!added) // 一整轮没有新增，控制闭包已经取完
            break;
    }
}

int main() {
    scanf("%d", &n);
    for (int k = 1; k <= n; k++) {
        int i, j;
        ll p;
        scanf("%d %d %lld", &i, &j, &p);
        own[i][j] += p; // 同一条持股边可能在输入里出现多次，必须累加
        if (i > v)
            v = i;
        if (j > v)
            v = j;
    }
    if (v < 1)
        v = 1; // 输入为空时也要有一个非空枚举范围

    for (int h = 1; h <= v; h++)
        solve_for(h);

    // 输出所有 h != s 的控制对，双重循环保证按 (h, s) 字典序
    for (int h = 1; h <= v; h++)
        for (int s = 1; s <= v; s++)
            if (ctrl[h][s] && h != s)
                printf("%d %d\n", h, s);
    return 0;
}

复杂度

对每个 $h$ 做不动点迭代：每轮扫描至多 $v$ 个候选 $s$，每个候选汇总至多 $v$ 家公司的持股，单轮 $O(v^2)$；每轮至少新增一个被控制公司（否则立即停止），所以至多迭代 $v$ 轮。总计

在上述实现里，汇总那一步是"$v$ 个候选 × $v$ 家公司"，即每轮 $O(v^2)$、每 $h$ 至多 $v$ 轮，故单个 $h$ 为 $O(v^3)$，全部 $h$ 合计 $O(v^4)$；代入 $v \leqslant 100$ 约 $10^8$ 次最坏情况的基本操作，而实际迭代轮数远小于 $v$（控制链通常很短），实测最大数据 concom8.in 不到 $0.5$ 秒。

• 空间复杂度：持股矩阵与控制矩阵各 $v^2$ 个布尔/整数，$O(v^2)$。

总结

• 题意核心：控制不是简单的传递闭包，而是"已控制集合所持股权的汇总超过 $50\%$"。先做持股图的传递闭包会漏解。
• 关键一步：把三条规则合写成单调扩张算子 $F_h(S)=\{h\}\cup\{s:\sum_{c\in S}\text{own}[c][s]>50\}$，从 $S=\{h\}$ 迭代到不动点即得 $h$ 的控制集。
• 连锁的含义：本轮新控制到的公司，其持股本轮即可计入；单调性保证迭代顺序不影响最终集合。
• 易错点：多条同向持股边要累加；判据是严格大于 $50\%$；输出不含控制自己的对，且保持 $(h,s)$ 字典序。