今天学姐讲课,lkp大佬神犇附体,成为了一秒切题真男人 传送门 我感觉我自己都不会 引例 给定n个变量和m个不等式,每个不等式形如 x[i] - x[j] <= a[k],求 x[n-1] - x[0] 的最大值。 (0 <= i, j < n) 例:n=4 然后经过认真的瞎搞计算就变成了这个鸭子: 我们会发现这个东西移项之后有没有和spfa的松弛操作十分的相似(我也不知道是怎么看出来的) spfa的松弛操作: 如果d[u] + w(u, v) < d[v], 则更新d[v] = d[u] + w(u, v); 然后再随便的瞎搞一下,就能把图画出来了... 正题(...