分数: 400 点
问题陈述
有 N 人们站在 x- 轴。 设 Person 的坐标 i be x_i。 对于每一个 i, x_i 是介于 0 和 10^9 (含)。 有可能不止一个人站在同一坐标处。
你将给予 M 有关这些人的职位的信息。 的 i第一条信息具有以下形式 (L_i, R_i, D_i)。 这意味着该人 R_i 位于人的右侧 L_i by D_i 距离单位,即 x_{R_i} - x_{L_i} = D_i 成立。
事实证明,其中一些 M 信息可能不正确。 判断是否存在一组值 (x_1, x_2, ..., x_N) 与给定的信息一致。
约束
- 1 \leq N \leq 100 000
- 0 \leq M \leq 200 000
- 1 \leq L_i, R_i \leq N (1 \leq i \leq M)
- 0 \leq D_i \leq 10 000 (1 \leq i \leq M)
- L_i \neq R_i (1 \leq i \leq M)
- If i \neq j,那么 (L_i, R_i) \neq (L_j, R_j) 和 (L_i, R_i) \neq (R_j, L_j).
- D_i 是整数。
输入
输入由标准输入按以下格式给出:
N M L_1 R_1 D_1 L_2 R_2 D_2 : L_M R_M D_M
输出
如果存在一组值 (x_1, x_2, ..., x_N) 与所有给定的信息一致,打印 Yes;如果不存在,则打印 No.
示例输入 1
3 3 1 2 1 2 3 1 1 3 2
示例输出 1
Yes
一些可能的值集 (x_1, x_2, x_3) 是 (0, 1, 2) 和 (101, 102, 103).
示例输入 2
3 3 1 2 1 2 3 1 1 3 5
示例输出 2
No
如果前两条信息正确, x_3 - x_1 = 2 成立,这与最后一条信息矛盾。
示例输入 3
4 3 2 1 1 2 3 5 3 4 2
示例输出 3
Yes
示例输入 4
10 3 8 7 100 7 9 100 9 8 100
示例输出 4
No
示例输入 5
100 0
示例输出 5
Yes