← 返回题目列表

AtCoder · abc373_d

G. 隐藏重量

中文机器翻译题面 查看原题

分数: 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