传送门 考虑将s−1s-1s−1向ttt连一条长度为vvv的边，ttt向s−1s-1s−1连一条长度为−v-v−v的边 先画图分析一下，发现出现如图这样的环，且环上的数之和不为000，就是不合法的。 发现如果这样一个环上面的边权之和为正，我们把这样的环上面的所有边取反，就可以得到一个负环。 如果边权之和为负，那么它就是负环。 于是SPFA\rm SPFASPFA判断图中是否有负环即可 12...