题解：法克 - 基于 Dilworth 定理的最大反链问题

问题重述

给定 $n$ 个英雄和 $m$ 个直接压制关系，压制关系具有传递性且无环。要求选出尽可能多的英雄，使得选出的英雄之间互相不压制。求最多能选出多少个英雄。

核心思路

1. 问题转化

压制关系构成一个有向无环图（DAG），其中边 $a \to b$ 表示 $a$ 压制 $b$。由于传递性，如果存在路径 $a \to \cdots \to b$，则 $a$ 压制 $b$。

我们需要在 DAG 中选出最大的点集，使得其中任意两点间不可达（即互相不压制）。这在偏序集理论中称为最大反链问题。

2. Dilworth 定理的应用

根据 Dilworth 定理：

在有限偏序集中，最大反链的大小等于最小链划分的大小。

这里：

• 反链：点集中任意两点不可达（互相不压制）
• 链：点集中任意两点可达（存在压制关系）
• 链划分：将图中所有点划分为若干个链

因此，我们只需要求出 DAG 的最小链划分，其大小就是答案。

3. 最小链划分的求解

对于 DAG，最小链划分可以通过二分图匹配来求解：

构造二分图：

• 将每个英雄 $i$ 拆成两个点：左部点 $L_i$ 和右部点 $R_i$
• 对于每条压制边 $a \to b$，连接 $L_a \to R_b$

关键结论：

DAG 的最小链划分大小 = $n$ - 二分图最大匹配数

因此： [ \text{答案} = n - \text{最大匹配数} ]

算法实现

网络流建模

代码使用最大流算法求解二分图匹配：

// 关键建图部分
for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    add(x, y + n, inf), add(y + n, x, 0);  // L_x -> R_y 边
}

for (int i = 1; i <= n; i++) {
    add(0, i, 1), add(i, 0, 0);           // 源点 -> L_i，容量1
    add(i + n, 2 * n + 1, 1), add(2 * n + 1, i + n, 0); // R_i -> 汇点，容量1
    add(i + n, i, inf);                    // 额外边，保证某些性质
    add(i, i + n, 0);
}

建图说明：

1. 压制关系边：$L_x \to R_y$，容量设为 $\infty$（或足够大）
2. 源点连接：源点 $s$ 连接到所有 $L_i$，容量 $1$
3. 汇点连接：所有 $R_i$ 连接到汇点 $t$，容量 $1$
4. 自连接边：$R_i \to L_i$，容量 $\infty$，确保某些匹配情况

算法流程

1. 输入：读取 $n, m$ 和压制关系
2. 建图：按上述方式建立网络流图
3. 计算最大流：使用 Dinic 算法计算从 $s$ 到 $t$ 的最大流
4. 输出答案：$n$ - 最大流量

时间复杂度

• 二分图共有 $2n$ 个顶点，$m + 3n$ 条边
• Dinic 算法在单位容量网络中的复杂度为 $O(E\sqrt{V})$
• 本题中 $V = O(n)$，$E = O(n+m)$
• 总复杂度为 $O((n+m)\sqrt{n})$，可以处理 $n \le 10^5$ 的数据

示例分析

以样例为例：

5 5
1 2
2 3
2 4
2 5
4 5

压制关系形成的 DAG：

1 → 2 → 3
    ↓
    4 → 5

二分图最大匹配为 $3$，因此： [ \text{答案} = 5 - 3 = 2 ]

可以选择英雄 $3$ 和 $5$，它们之间没有压制关系。

正确性证明

1. Dilworth 定理保证了最大反链大小等于最小链划分大小
2. 最小路径覆盖问题可以转化为二分图匹配：
   • DAG 中的每条路径对应二分图中的一组匹配
   • 路径数最少时匹配数最大
3. 最小链划分（最小路径覆盖）大小为 $n - \text{最大匹配数}$

总结

本题通过 Dilworth 定理将看似复杂的压制关系问题转化为经典的图论问题。关键步骤：

1. 将压制关系建模为 DAG
2. 应用 Dilworth 定理，问题转化为求最小链划分
3. 通过二分图匹配求解最小链划分
4. 使用网络流（最大流）算法高效求解二分图匹配

算法的时间复杂度和空间复杂度均能满足题目要求，可以处理 $n \le 10^5$ 的大规模数据。