【并查集、二分图匹配】ABC434E
WanderOvO
·
·
题解
【并查集、二分图匹配】ABC434E
原题链接
简要题意
有 n 只兔子，第 i 只兔子初始位于坐标 X_i，其跳跃能力为 R_i。每只兔子必须跳跃一次，可以跳到 X_i - R_i 或 X_i + R_i。
求所有兔子跳跃后，最终占据的不同坐标数量的最大值。
## 思路
### 1. 二分图匹配模型
我们可以将这个问题建模为**二分图最大匹配**：
- **左侧点集**：$n$ 只兔子。
- **右侧点集**：所有可能的跳跃坐标（即所有的 $X_i - R_i$ 和 $X_i + R_i$，需离散化）。
- **边**：每只兔子向它能到达的两个坐标连边。
由于 $n = 2 \times 10^5$，右侧点数最多 $2n$，虽然理论复杂度 $O(E\sqrt{V})$ 在单位容量网络下表现优秀（Dinic 实测约 670ms 可过），但我们仍有更优雅的 $O(n \alpha(n))$ 解法。
### 2. 图论结构转化（并查集优化）
由于每只兔子（边）恰好连接两个坐标（点），我们可以将左侧的兔子视为连接两个右侧坐标点的**边**。
这样，问题转化为：在一个由坐标点作为顶点、兔子作为边组成的图中，**为每条边指定一个端点**，使得被指定的不同端点数最大。
对于图中的每一个**连通分量**，设其点数为 $V$，边数为 $E$：
- **若该分量是一棵树** ($E = V - 1$)：由于边数少于点数，最多只能占领 $E$ 个点（即 $V-1$ 个点）。
- **若该分量包含环** ($E \ge V$)：根据基环树或更复杂图的性质，我们总能通过定向使得该分量的所有 $V$ 个顶点都被占领。
因此，每个连通分量的贡献为 $\min(V, E)$。最终答案即为所有连通分量贡献的总和：
$$\sum \min(V_{\text{component}}, E_{\text{component}})$$
利用并查集可以在扫描兔子的同时，动态维护每个连通分量的点数和边数，实现复杂度极低。