103733: [Atcoder]ABC373 D - Hidden Weights

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:12 Solved:0

Description

Score : $400$ points

Problem Statement

You are given a directed graph with $N$ vertices and $M$ edges. The $j$-th directed edge goes from vertex $u_j$ to vertex $v_j$ and has a weight of $w_j$.

Find one way to write an integer between $-10^{18}$ and $10^{18}$, inclusive, to each vertex such that the following condition is satisfied.

  • Let $x_i$ be the value written on vertex $i$. For all edges $j=1,2,\dots,M$, it holds that $x_{v_j} - x_{u_j} = w_j$.

It is guaranteed that at least one such assignment exists for the given input.

Constraints

  • $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$, then $(u_i, v_i) \neq (u_j, v_j)$ and $(u_i, v_i) \neq (v_j, u_j)$
  • $|w_j| \leq 10^9$
  • All input values are integers.
  • There exists at least one assignment satisfying the conditions.

Input

The input is given from Standard Input in the following format:

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

Output

Let $x_i$ be the integer written on vertex $i$. Print $x_1, x_2, \dots, x_N$ in this order, separated by spaces, on a single line. If there are multiple solutions, you may print any of them.


Sample Input 1

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

Sample Output 1

3 5 2

By setting $x = (3, 5, 2)$, we have $x_2 - x_1 = w_1 = 2$, $x_2 - x_3 = w_2 = 3$, $x_3 - x_1 = w_3 = -1$, satisfying the conditions.

For example, $x = (-1, 1, -2)$ is also a valid answer.


Sample Input 2

4 2
2 1 5
3 4 -3

Sample Output 2

5 0 6 3

For example, $x = (0, -5, 4, 1)$ and $x = (5, 0, 4, 1)$ are also valid answers.


Sample Input 3

5 7
2 1 18169343
3 1 307110901
4 1 130955934
2 3 -288941558
2 5 96267410
5 3 -385208968
4 3 -176154967

Sample Output 3

200401298 182231955 -106709603 69445364 278499365

Output

得分: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$
  • 如果$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
		  

加入题单

上一题 下一题 算法标签: