分数: 400 点
问题陈述
给你一个有向图 N 顶点和 M 边缘。这 j- 第一条有向边从顶点出发 u_j 到顶点 v_j 的重量为 w_j.
找到一种在之间写入整数的方法 -10^{18} 和 10^{18}(含)到每个顶点,以满足以下条件。
- 让 x_i 是写在顶点上的值 i。对于所有边缘 j=1,2,\dots,M,它认为 x_{v_j} - x_{u_j} = w_j.
保证给定输入至少存在一个这样的分配。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq \min\{2 \times 10^5,N(N-1)/2\}
- 1 \leq u_j, v_j \leq N
- u_j \neq v_j
- If i \neq j,那么 (u_i, v_i) \neq (u_j, v_j) 和 (u_i, v_i) \neq (v_j, u_j)
- |w_j| \leq 10^9
- 所有输入值均为整数。
- 存在至少一个满足条件的分配。
输入
输入由标准输入按以下格式给出:
N M u_1 v_1 w_1 u_2 v_2 w_2 \vdots u_M v_M w_M
输出
让 x_i 是写在顶点上的整数 i。打印 x_1, x_2, \dots, x_N 按此顺序,用空格分隔,在一行上。如果有多个解决方案,您可以打印其中任何一个。
示例输入 1
3 3 1 2 2 3 2 3 1 3 -1
示例输出 1
3 5 2
通过设置 x = (3, 5, 2),我们有 x_2 - x_1 = w_1 = 2, x_2 - x_3 = w_2 = 3, x_3 - x_1 = w_3 = -1,满足条件。
例如, x = (-1, 1, -2) 也是一个有效的答案。
示例输入 2
4 2 2 1 5 3 4 -3
示例输出 2
5 0 6 3
例如, x = (0, -5, 4, 1) 和 x = (5, 0, 4, 1) 也是有效的答案。
示例输入 3
5 7 2 1 18169343 3 1 307110901 4 1 130955934 2 3 -288941558 2 5 96267410 5 3 -385208968 4 3 -176154967
示例输出 3
200401298 182231955 -106709603 69445364 278499365