差分约束系统定义

一个系统由n个变量和m个约束条件组成，形成m个形如ai-aj≤k的不等式
(i,j∈[1,n],k为常数),则称其为差分约束系统(system of difference constraints)

解释：其实就是一堆不等式，然后求出一组解。不等式形如 Xi-Xj<=Ck  (i!=j)然后我们需要求出一组解X1~Xn有{
   A1~An},而对于常数d，{
   A1+d~An+d}也是它的一组解，因为做差可以将d消除

在这里插入图片描述

差分约束与SPFA

利用差分约束解决问题的时候，我们常常把它化为求最短路径问题，因为要把不等 式化为我们想要的形式，所以常常会有负数，即是会出现负边权的问题，所以Floyd和Dijkstra通常无法解决，我们就用Bellman-Ford算法来解决此类问题。

常见的不等式转换

区间选点问题

给定一个数轴上的 n 个区间，要求在数轴上选取最少的点使得第 i 个区间 [ai, bi] 里至少有 ci 个点

Input

输入第一行一个整数 n 表示区间的个数，接下来的 n 行，每一行两个用空格隔开的整数 a，b 表示区间的左右端点。1 <= n <= 50000， 0 <= ai <= bi <= 50000 并且 1 <= ci <= bi - ai+1。

Output

输出一个整数表示最少选取的点的个数

Sample Input

53 7 38 10 36 8 11 3 110 11 1

Sample Output

分析：之前用贪心算法写过此题。对于差分约束解决此题的具体过程我们不妨把ai bi看为dis[v[i]]和dis[u[i]]，从而转化为图中的点，求解最少的选取点的个数，就是最短路径的问题，满足每个区间至少有Ci个点，设置这个区间权值为Ci,那么dis[v[i]]-dis[u[i]]>=ci,实现了路径压缩。

Codes

#include
   
    #include
    
     using namespace std;const int Inf=-1e6;const int maxn=1e5;int vis[maxn],head[maxn],tot=0,dis[maxn],n,a,b,c,ma=maxn,mb=0;struct edge{
    int to,next,w;};edge e[maxn*2];queue
     
       Q;//ci<=bi-ai+1//构造为  -bi<=-(ai-1)+(-ci) void Init(){
   //初始化  for(int i=0;i
      
       >n; Init(); for(int i=0;i
       
        >a>>b>>c;  add_edge(a,b+1,c);//让a从0开始，实际上是右端点包含  //所以有c<=b-a+1,也可以构造add_edge(a,b+1,c)  //dis[b]-dis[a-1]>=c or dis[b+1]-dis[a]>=c   ma=min(a,ma);  mb=max(b+1,mb); }//0<=dis[i+1]-dis[i]<=1 for(int i=ma;i<=mb;i++){
     add_edge(i,i+1,0);  add_edge(i+1,i,-1); } spfa(ma); cout<
        
         <