Abc373 D - Hidden Weights

问题陈述

给你一个有向图，图中有 N 个顶点和 M 条边。第 j 条有向边从顶点 u j 到顶点 v j，权重为 wj。

请找出一种方法，在每个顶点写入一个介于 -10 18 和 10 18 之间的整数，从而满足以下条件。

让 x i 是写在顶点 i 上的值。

j=1,2,...,M，则 x v j -x u j =w j 成立。

保证给定输入至少存在一个这样的赋值。

约束条件

2≤N≤2×10 5

 1≤M≤min{2×10 5 ,N(N-1)/2}

1≤u 

j ,v j ≤Nu j !=v j 如果 i!=j ，那么 (u i ,v i ) !=(u j ,v j ) 并且 

(u i ,v i )!=(v j ,u j )∣w j ∣≤10 9 

所有输入值均为整数。

至少存在一个满足条件的赋值。

输入

输入内容由标准输入法提供，格式如下：

N 

M

u 1 v 1 w 1 

u 2 v 2 w 2 

⋮

u M v M w M 

输出

让 x i 是写在顶点 i 上的整数。按此顺序将 x 1,x 2 ,...,x N 打印在一行上，中间用空格隔开。如果有多个解，可以打印任意一个。

输入示例 1

3 3

1 2 2

3 2 3

1 3 -1

通过DeepL.com（免费版）翻译

---

就是求n元一次方程组的解，这里面我用的有向图，然后用拓扑排序的办法做的，结果老是错，看了题解，是用的无向图的办法+vis数组，每次更新函数值的办法来做的。只是有点不理解为什么这样做出来的答案一定是正确的。。当有一个元素未访问过的话，那么这个元素一定就是0，然后其他跟他有关系的元素就根据他们的相关的大小，来确定值的。