差分约束基础应用

差分约束用于解决一种特殊的 $n$ 元一次不等式组，实际是应用了最短路算法的松弛的思想。借鉴其思想可以解决很多性质相类似的题目。 相关讲解可以参考[这篇文章](https://www.luogu.com.cn/blog/80049/system-of-difference-constraints)或者模板题题解区。 ---------- 本题单收集了一些差分约束的题目，具体如下： - [P5960 【模板】差分约束算法](https://www.luogu.com.cn/problem/P5960) 模板题入门。 - [P1993 小 K 的农场](https://www.luogu.com.cn/problem/P1993) - [P3275 [SCOI2011]糖果](https://www.luogu.com.cn/problem/P3275)（本题正解不是差分约束但是可以当做基础题练手） 对不等式进行简单的变形即可做出，思维难度较低。 - [SP116 INTERVAL - Intervals](https://www.luogu.com.cn/problem/SP116) - [P2294 [HNOI2005]狡猾的商人](https://www.luogu.com.cn/problem/P2294) 不那么显然的差分约束题目，需要自己构造不等式，但是依然不难想。 - [P2474 [SCOI2008]天平](https://www.luogu.com.cn/problem/P2474) - [P4926 [1007]倍杀测量者](https://www.luogu.com.cn/problem/P4926) 比较进阶的差分约束题，需要一定的技巧和足够的码力。 ---------- #### 更多题目有待补充