AT_abc373_d [ABC373D] Hidden Weights

题目描述

给定一个有 $N$ 个顶点、$M$ 条边的有向图。第 $j$ 条有向边从顶点 $u_j$ 指向顶点 $v_j$，权值为 $w_j$。

请找出一种方法，将 $-10^{18}$ 到 $10^{18}$ 之间的整数写在每个顶点上，使得满足以下条件：

• 设顶点 $i$ 上写的数为 $x_i$。对于所有边 $j=1,2,\dots,M$，都有 $x_{v_j} - x_{u_j} = w_j$。

保证对于给定的输入，至少存在一种满足条件的写法。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$
$u_1$ $v_1$ $w_1$
$u_2$ $v_2$ $w_2$
$\vdots$
$u_M$ $v_M$ $w_M$

输出格式

请输出一行，用空格分隔的 $x_1,x_2,\dots,x_N$，其中 $x_i$ 表示写在顶点 $i$ 上的整数。若有多种答案，输出任意一种均可。

输入输出样例 #1

输入 #1

3 3
1 2 2
3 2 3
1 3 -1

输出 #1

3 5 2

输入输出样例 #2

输入 #2

4 2
2 1 5
3 4 -3

输出 #2

5 0 6 3

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $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$
• 若 $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$
• 输入均为整数
• 保证至少存在一种满足条件的写法

样例解释 1

例如取 $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

例如取 $x=(0,-5,4,1)$ 或 $x=(5,0,4,1)$，都是正确答案。

由 ChatGPT 4.1 翻译