[POJ-1201]Intervals

题目传送门

差分约束系统很棒的应用，首先运用前缀和的思想，令s[k]为0~k中被选出来数的个数，则s[b[i]]>=s[a[i]-1]+c,这样会有一个问题，那就是下标可能会出现负数，因此我们可以改变前缀和表示的方法，设s[k]为0~k-1中被选出来的数，则约束条件可以转化为：s[b[i]+1]-s[a[i]]>=c;简单处理后可得到s[b[i]+1]>=s[a[i]+c;但是只有这一个约束条件远远不够，这只是数据硬性规定的，而还有一些条件是隐含的，有下面两种隐含条件也需要加入约束系统：1）s[k]是前缀和的形式，所以s[k]不可能比s[k-1]小，可得到s[k]>=s[k-1]+0;（2）s[k]最多比s[k-1]多选k这一个数，所以s[k]<=s[k-1]+1，简单处理后得到s[k-1]>=s[k]-1,加入以上两种边后SPFA跑最长路求解即可差分约束系统很棒的应用，首先运用前缀和的思想，令s[k]为0~k中被选出来数的个