#P5960. 【模板】差分约束算法

【模板】差分约束算法

题目描述

给出一组包含 mm 个不等式,有 nn 个未知数的形如:

$$\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases} $$

的不等式组,求任意一组满足这个不等式组的解。

输入格式

第一行为两个正整数 n,mn,m,代表未知数的数量和不等式的数量。

接下来 mm 行,每行包含三个整数 c,c,yc,c',y,代表一个不等式 xcxcyx_c-x_{c'}\leq y

输出格式

一行,nn 个数,表示 x1,x2xnx_1 , x_2 \cdots x_n 的一组可行解,如果有多组解,请输出任意一组,无解请输出 NO

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

提示

样例解释

$\begin{cases}x_1-x_2\leq 3 \\ x_2 - x_3 \leq -2 \\ x_1 - x_3 \leq 1 \end{cases}$

一种可行的方法是 x1=5,x2=3,x3=5x_1 = 5, x_2 = 3, x_3 = 5

$\begin{cases}5-3 = 2\leq 3 \\ 3 - 5 = -2 \leq -2 \\ 5 - 5 = 0\leq 1 \end{cases}$

数据范围

对于 100%100\% 的数据,1n,m5×1031\leq n,m \leq 5\times 10^3104y104-10^4\leq y\leq 10^41c,cn1\leq c,c'\leq nccc \neq c'

评分策略

你的答案符合该不等式组即可得分,请确保你的答案中的数据在 int 范围内。

如果并没有答案,而你的程序给出了答案,SPJ 会给出 There is no answer, but you gave it,结果为 WA;
如果并没有答案,而你的程序输出了 NO,SPJ 会给出 No answer,结果为 AC;
如果存在答案,而你的答案错误,SPJ 会给出 Wrong answer,结果为 WA;
如果存在答案,且你的答案正确,SPJ 会给出 The answer is correct,结果为 AC。