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