题意: 知道了数轴上的n个区间，每个区间都是连续的int区间，现在要在数轴上任意取一堆元素，构成一个元素集合V要求每个区间和元素集合V的交集至少有两个不同的元素

        求集合V最小的元素个数。

转一分析：（差分约束）

设s[x] = 从0 到x 的所有在集合中的数的个数

则ai到bi的个数即S[bi] - S[ai-1]。

因此有

(1) S[bi] - S[ai-1] >= 2。

又根据s[x]本身的性质，

后面的一定不比前面的小，后面的最多比前面多一，有：

(2)  s[i + 1] - s[i] >= 0

(3)  s[i + 1] - s[i] <= 1

故建图,使图中每一组边，均满足（注意三条式子的不等号方向要一致，这个很重要）:

S[ai - 1] <= S[bi] - 2

S[i] <= S[i - 1] + 1

S[i - 1] <= S[i]

上面三式，可把s[x]看作源点（假设存在）到各点的最短距离，初始化为0；

常数为边(ai – 1，bi)的边权

当存在不满足这三条式子的边时，对这条边进行Relax操作，更新不等号左边的变量。

其实就是Bellman-Ford算法的核心部分

if( S[ai - 1] > S[bi] – 2 )   S[ai - 1] = S[bi] – 2 ；

if( S[i] > S[i - 1] + 1 )   S[i] > S[i - 1] + 1 ；

if( S[i - 1] > S[i] )   S[i - 1] = S[i] ；

 

最后源点到最大顶点的距离减去源点到最小顶点的距离就是所求（其实一个单位距离就代表V中的一个元素；最小顶点到最大顶点其实就是所有输入的区间中，最小的左端点到最大的右端点这个范围）。

#include
     
      #include
      
       #define INF 0x1f1f1f1fstruct node{    int s,e;}q[10001];int dis[10001];int n;int low,high;int main(){    int a,b,i,flag;    while(scanf("%d",&n)!=EOF)    {        low=INF;        high=0;        for(i=0;i
       
        high)                high=q[i].e;            dis[i]=0;        }        flag=1;        while(flag)        {            flag=0;            for(i=0;i
        
         dis[q[i].e]-2)                {                    dis[q[i].s]=dis[q[i].e]-2;                    flag=1;                }            for(i=low;i
         
          dis[i]+1)                {                    dis[i+1]=dis[i]+1;                    flag=1;                }            for(i=high-1;i>=low;i--)                if(dis[i]>dis[i+1])                {                    dis[i]=dis[i+1];                    flag=1;                }        }        printf("%d\n",dis[high]-dis[low]);    }    return 0;}