IOI2026 集训队互测 D1T3 题解

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

有两种询问：

$o \in \{1, 2\}, 1 \leq n \leq 3 \times 10^5, 0 \leq m \leq \min\left(\dfrac{n(n-1)}{2}, 10^6\right)$，保证 $G$ 无重边自环，保证 $G$ 中每条边的权值均 $\in [1, 10^9] \cap \mathbb{Z}$。

不失一般性的，假设 $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$ 不连通的情况，可以分开考虑每个连通块的构造 / 判定。