P14252 [集训队互测 2025] 集你太美

人面不知何处去，桃花依旧笑春风。

给定一张 $ n $ 个结点的无向完全图 $ G $，边 $ (i, j) $ 带非负整数权 $ v_{i,j} $，保证 $ v_{i,i} = 0 $，$ v_{i,j} = v_{j,i} $。 同时，每个结点有一个非负整数变量 $ w_i $。 定义对一个点 $ i $ 进行一次**收集操作**为，将 $ w_i $ 的值加上 $ \sum_j v_{i,j} $，并将 $ w_j $ 的值减去 $ v_{i,j} $。称一次对点 $ i $ 的收集操作**合法**，当且仅当操作前 $ w_j \ge v_{i,j} $。 在图 $ G $ 上称一组点权**收集-free**，当且仅当以这组点权为初始状态，存在一种方式，能够进行**无限次**合法的收集操作。 你有**两种**任务。第一种，**构造**一组点权 $ w'_i $，使得 $ w'_i $ 收集-free，且**最小化** $ \sum_i w'_i $；第二种，给定一组点权 $ w'_i $，你需要**判断** $ w'_i $ 是否 收集-free。

第一行一个正整数 $ o $，表示你的任务类型。 第二行一个正整数 $ n $ 和一个非负整数 $ m $，表示 $ G $ 的结点数和边权非 0 的边数。 接下来的 $ m $ 行，每行 3 个正整数 $ i, j, v $，表示在 $ i $ 和 $ j $ 间的边边权为 $ v $。 若 $ o = 2 $，接下来有一行 $ n $ 个非负整数 $ w'_i $，代表你需要判断是否 收集-free 的一组点权。

若 $ o = 1 $，输出一行 $ n $ 个非负整数 $ w'_i $，代表你构造的点权。你应当保证 $ 0 \le w'_i \le 10^{18} $。 若 $ o = 2 $，输出一行 YES 或 NO，代表 $ w'_i $ 是否 收集-free。

### 样例解释 当初始点权与样例输出 1 中构造的一致时，可以发现依次操作 $ 3, 5, 4, 2, 3, 4, 1, 5, 2, 1 $ 号点后，所有点的点权与初始情况一致，且这些操作均合法，故可以进行无限次合法的收集操作。 容易注意到，样例输入 2 给出的点权为样例输出 1 中构造的点权 $+1$，故显然合法。 ### 提示 在下发文件中含有 `checker.exe`（linux 格式下为 `checker`），你可以使用它来验证你的输出是否正确。具体的使用方式为 `checker collect.in collect.out collect.out`，其中 `collect.in` 和 `collect.out` 为与 `checker.exe` 在相同目录下的输入输出文件。 | 返回值 | 信息 | |:------:|:----:| | 0 | 输出正确 | | 1 | 你构造的方案中 $ \sum w'_i $ 比正确的更小 | | 2 | 你构造的方案中 $ \sum w'_i $ 比正确的更大 | | 3 | 你构造的方案不是 收集-free 的 | | 4 | 你输出了 YES 和 NO 以外的字符串 | | 5 | 你对于是否 收集-free 的判断错误 | ### 限制与约定 对于所有数据，$ o \in \{1, 2\} $，$ 1 \le n \le 3 \times 10^5 $，$ 0 \le m \le \min\left(10^6, \frac{1}{2}n(n-1)\right) $，$ 1 \le i < j \le n $，$ (i, j) $ 互不相同，$ 1 \le v \le 10^9 $，$ 0 \le w'_i \le 10^{18} $。 注意在某些数据中，只考虑边权非 0 的边的情况下，图可能不连通。 | Subtask 编号 | $ n $ 的上界 | $ m $ 的上界 | 特殊性质 | 分值 | |:------------:|:-------------:|:-------------:|:--------:|:----:| | 1 | $10$ | $20$ | 无特殊性质 | $10$ | | 2 | $20$ | $100$ | ^ | $10$ | | 3 | $300$ | $2000$ | ^ | $10$ | | 4 | $3\times 10^5$ | $ n - 1 $ | $ o = 1 $，非 $0$ 边构成一棵树 | $10$ | | 5 | ^ | $\min\left(10^6, \frac{1}{2}n(n-1)\right)$ | $ o = 1 $ | $30$ | | 6 | ^ | ^ | $ o = 2 $ | $20$ | | 7 | ^ | ^ | 无特殊性质 | $10$ |