IOI2026 集训队互测 D1T3 题解

· · 题解

给定一张 n 个点 m 条边的无向带权图 G，定义 (w_1, w_2, \dots, w_n) 是 收集-free 的当且仅当可以无限次做以下操作：

有两种询问：

-------------------------------- 不失一般性的，假设 $G$ 连通。 **Observation 1**：若 $(w_1, w_2, \dots, w_n)$ 是 **收集-free** 的，那么 $G$ 中的每个点都一定被操作了无穷多次。 证明：任取一个无穷长度的操作序列，若观察不成立则一定存在一条边 $(u, v, x)$ 使得 $u$ 被操作了无穷多次，$v$ 被操作了有限次，显然 $w_v$ 一定是在每次操作 $u$ 的时候都要减去 $x$，最终 $w_v$ 一定会被减至 $< 0$。 **Observation 2**：不失一般性的，设 $i(1 \leq i < n)$ 第一次操作的时间早于 $i + 1$，则一定有 $w_i \geq \displaystyle \sum_{j = 1}^{i - 1}W(i, j)$，其中 $W(i, j)$ 为 $i, j$ 之间边的边权，若无边则为 $0$。 证明：显然 $i$ 操作之前 $1 \sim i - 1$ 都被操作了至少一次，$w_i$ 至少要被减掉 $\displaystyle \sum_{j = 1}^{i - 1}W(i, j)$。 **Observation 3**：**Observation 2** 中提到的必要条件是充分的。 证明：将 $G$ 按 $1, 2, \dots, n$ 的拓扑序定向为一张 DAG，每次任取 DAG 中一个入度为 $0$ 的点进行操作即可，最终将原来的拓扑序 $1, 2, \dots, n$ 旋转一位变成 $n, 1, 2, \dots, n - 1$（即对应接下来的操作顺序）并将图 $G$ 重新定向，容易发现 **Observation 2** 中提到的条件仍然成立。 基于这三个观察我们可以发现 $\displaystyle \sum_{i = 1}^{n}w_i$ 的下界为 $G$ 的所有边权之和，并且可以通过将图定向为一个 DAG 之后将每个点的点权赋值为其入边的边权之和来构造 $o = 1$ 的答案。 对于 $o = 2$，可以考虑图 $G$ 按上述观察定向后的任意一个出度为 $0$ 的点 $u$，显然该点满足 $w_u \geq \displaystyle\sum_{(u, v, x) \in E}{x}$，将 $u$ 删掉递归判定即可，若 $G$ 最终被删空则有解，否则无解。 对于 $G$ 不连通的情况，可以分开考虑每个连通块的构造 / 判定。