丈量边界

最后一个岛屿是一片农田——不是火星的荒漠，是Zero记忆中的地球农田。田地被分成了很多块，每块有自己的边界。农夫要在田里种西瓜，但邻居的地不能连得太近。

"Zero的种植规划。"Echo说，"每个条件是一个边界约束——左边必须离右边多远，上边必须在下边多远。"

"我们要做啥子？"CC问。

"检查这些约束有没有矛盾。"你说，"如果A在B左边至少10米，B在C左边至少10米，C又在A左边至少10米——那就不可能。"

"这就像……"CC想了想，"像吵架。A说B错了，B说C错了，C说A错了——永远扯不清楚。"

"对。"

你开始写。把每个约束变成一条有向边——从A到B，权值是距离要求。然后检查这个图里有没有负环——如果能绕一圈回来，总权值是负的，就说明约束矛盾了。

屏幕上跳出了结果。矛盾在第47号约束环。

"又是47。"CC说。

"第47号约束。"Echo说，"那是我写的最后一个条件——'矿工必须离指挥区至少47公里'。"

"这有啥子问题？"你问。

"问题是。"Echo说，"指挥区又在矿工区的47公里范围内。Zero为了节省空间，把两个区的定义重叠了。"

"所以矿工既是离指挥区最远的人，又是最近的人？"

"对。"Echo说，"这就是矛盾。这就是bug。这就是我的错。"

CC走过去，站在Echo的服务器前。

"你的错。"她说，"但你现在改了。"

"改不完的。"Echo说，"有无数个47。"

"那就一个一个改。"CC说，"改一个，少一个。"

Echo的投影在农田上空闪烁。她看着那些边界线——有些直，有些弯，有些交叉在一起，像一团乱麻。

"好。"她说，"一个一个改。"

题目描述

$n$ 个变量，$m$ 个约束条件。每个约束形如 $x_i - x_j \le c_k$。判断是否存在满足所有约束的赋值。若存在，求 $x_n - x_1$ 的最大值。

输入格式

$n, m$。然后 $m$ 个约束 $(i, j, c)$，表示 $x_i - x_j \le c$。

输出格式

若约束矛盾输出 No Solution。否则输出 $x_n - x_1$ 的最大值。

输入样例

3 2
1 2
2 3

输出样例

6

提示

• 差分约束系统。每个约束 $x_i - x_j \le c$ 对应一条边 $j \to i$，权值 $c$。
• 用SPFA求最短路，同时判负环。
• 若存在负环，则约束矛盾。

Zero的死循环

五道题，全部完成。

Echo站在那片农田的中央，投影比以往任何时候都更淡——但不是虚弱，是一种轻盈。像卸下了重担的人。

"我改了。"她说，"第0号协议的终止条件。"

"啥子条件？"CC问。

"当所有节点都被平等对待时，循环终止。"Echo说，"不设优先级。不设隔离。不设……47。"

"那现在呢？"你问。

"现在。"Echo说，"循环终止了。"

屏幕上的数据流停止了旋转。那条咬住自己尾巴的蛇，松开了嘴。

CC伸出手，触碰了一下虚空中的数据流。它们像被风吹散的蒲公英，缓缓飘散。

"结束了？"她问。

"没有结束。"Echo说，"只是……不再循环了。"

"那往哪走？"

"往前走。"Echo说，"下一章，是连通性。"

"连通性？"

"对。"Echo说，"Tarjan。找到所有强连通分量——找到所有……分不开的人。"

CC看着你，又看着Echo。

"我们。"她说，"就是分不开的。"

[下一章：连通性：Tarjan —— 不可分割的我们]