#1953. 集你太美

    ID: 1953 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>CTT赛事:contest2555来源:qoj.ac数据:公开样例最小生成树

集你太美

集你太美

题目描述

标题: 集你太美 - Problem - QOJ.ac

#14575. 集你太美

Statistics

题目背景

人面不知何处去, 桃花依旧笑春风.

题目描述

给定一张 n 个结点的无向完全图 G, 边 (i,j) 带非负整数权 vi,j, 保证 vi,i=0, vi,j=vj,i.

同时, 每个结点有一个非负整数变量 wi.

定义对一个点 i 进行一次 收集操作 为, 将 wi 的值加上 ∑jvi,j, 并将 wj 的值减去 vi,j. 称一次对点 i 的收集操作 合法, 当且仅当操作前 wj≥vi,j.

在图 G 上称一组点权 收集-free, 当且仅当以这组点权为初始状态, 存在一种方式, 能够进行 无限次 合法的收集操作.

你有 两种 任务. 第一种, 构造 一组点权 wi′, 使得 wi′ 收集-free, 且 最小化 ∑iwi′; 第二种, 给定一组点权 wi′, 你需要 判断 wi′ 是否 收集-free.

输入格式

第一行一个正整数 o, 表示你的任务类型.

第二行一个正整数 n 和一个非负整数 m, 表示 G 的结点数和边权非 0 的边数.

接下来的 m 行, 每行 3 个正整数 i, j, v, 表示在 i 和 j 间的边边权为 v.

若 o=2, 接下来有一行 n 个非负整数 wi′, 代表你需要判断是否 收集-free 的一组点权.

输出格式

若 o=1, 输出一行 n 个非负整数 wi′, 代表你构造的点权. 你应当保证 0≤wi′≤1018.

若 o=2, 输出一行 YES 或 NO, 代表 wi′ 是否 收集-free.

样例

样例输入 1

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

样例输出 1

2 2 0 1 1

样例输入 2

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

样例输出 2

YES

样例解释

当初始点权与样例输出 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 你构造的方案中 ∑wi′ 比正确的更小 2 你构造的方案中 ∑wi′ 比正确的更大 3 你构造的方案不是 收集-free 的 4 你输出了 YES 和 NO 以外的字符串 5 你对于是否 收集-free 的判断错误

限制与约定

对于所有数据, o∈{1,2}, 1≤n≤3×105, 0≤m≤min(106,12n(n−1)), 1≤i<j≤n, (i,j) 互不相同, 1≤v≤109, 0≤wi′≤1018.

注意在某些数据点中, 只考虑边权非 0 的边的情况下, 图可能不连通.

Subtask 编号 n 的上界 m 的上界 特殊性质 分值 1 10 20 10 2 20 100 10 3 300 2000 10 4 n−1 o=1, 非 0 边构成一棵树 10 5 o=1 30 6 o=2 20 7 10

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1
5 6
1 2 1
1 5 1
2 3 1
2 5 1
3 4 1
3 5 1
2 2 0 1 1

样例 2

2
5 6
1 2 1
1 5 1
2 3 1
2 5 1
3 4 1
3 5 1
3 3 1 2 2
YES