差分约束

· · 个人记录

形如x_i-x_j\leqslant c的不等式，从j向i连一条边权为c的边，从0向每个节点连边权为0的有向边，然后从0号点开始进行单源最短路径，若出现负环则问题无解。这样求出的是一组负数解，最后需要根据题意处理一下。