把每条约束
ai−aj=k看成点 i,j 之间的一条差分关系。
如果我们设某个连通块内任选一个点的值为基准,那么这个连通块中所有点的值都会被唯一确定到“相对值”。这类问题本质上就是:
在幻光实验室中,Alice 需要构造一个长度为 n 的正整数数组 a,其中每个元素 ai>0。但她手中有 m 条魔法约束,每条约束给出三元组 (i,j,k),要求 ai−aj=k。 请你判断是否存在满足所有约束且 1≤ai≤1018 的数组 a。若存在则输出任意一个符合条件的数组;否则输出 -1。
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤105) 代表测试组数,每组测试数据描述如下:
第一行输入两个整数 n,m(1≤n,m≤2×105);
接下来 m 行,每行输入三个整数 i,j,k (1≤i,j≤n,−106≤k≤106)
保证所有测试中 n 的总和不超过 5×105。m 的总和不超过 5×105。
对于每组测试数据,输出一行:
若存在满足所有约束且 1≤ai≤1018 的数组a,则输出 n 个正整数 a1,a2,…,an;否则输出 -1。
输入
2
3 2
1 2 1
2 3 1
2 2
1 2 100
2 1 1
输出
3 2 1
-1
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.