差分约束基础应用

差分约束用于解决一种特殊的 n 元一次不等式组,实际是应用了最短路算法的松弛的思想。借鉴其思想可以解决很多性质相类似的题目。

相关讲解可以参考这篇文章或者模板题题解区。

本题单收集了一些差分约束的题目,具体如下:

模板题入门。

对不等式进行简单的变形即可做出,思维难度较低。

不那么显然的差分约束题目,需要自己构造不等式,但是依然不难想。

比较进阶的差分约束题,需要一定的技巧和足够的码力。

更多题目有待补充


  1. P5960 - 【模板】差分约束
  2. P1993 - 小 K 的农场
  3. P3275 - [SCOI2011] 糖果
  4. SP116 - INTERVAL - Intervals
  5. P2294 - [HNOI2005] 狡猾的商人
  6. P2474 - [SCOI2008] 天平
  7. P4926 - [1007] 倍杀测量者