题目链接：POJ1716-Integer Intervals

题意：给出数轴上的n个区间，现在要在数轴上任意取一堆元素，构成一个元素集合V，要求每个区间和元素集合V的交集至少有两个不同的元素，求集合V最小的元素个数。

题解：

差分约束跑最短路。

根据题意，我们可以设 bm[x] 为 [0,x] 这个区间内满足的条件的数的个数，因此就有 st[i] 到 ed[i] 中的个数为 bm[ed[i]+1] - bm[st[i]] 个

然后我们可以推出一个不等式：bm[ed[i]+1]-bm[st[i]]>=2​

然后根据$bm[x]$的性质，可以推出：0 <= bm[i+1]-bm[i] <= 1​

由以上的不等式我们可以建图（差分约束系统）：

bm[st[i]] <= bm[ed[i]+1]-2​

bm[i] <= bm[i-1]+1​

bm[i-1] <= bm[i]​

可以把 bm[x] 看作源点，常数为 V（st[i],ed[i]+1）的边权，建图。

参考代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int st[10009],ed[10009],bm[10009];
int main()
{
    while(scanf("%d",&n)==1)
    {
        int maxV=-1,minV=10009;
        for(int i=1;    i<=n;   i++)
        {
            scanf("%d%d",st+i,ed+i);
            ed[i]++;
            maxV=max(maxV,ed[i]);
            minV=min(minV,st[i]);
            bm[i]=0;
        }
        bool flag=1;
        while(flag)
        {
            flag=0;
            for(int i=1;    i<=n;   i++)
                if(bm[st[i]]>bm[ed[i]]-2)
                    bm[st[i]]=bm[ed[i]]-2,flag=1;
            for(int i=minV; i<maxV; i++)
                if(bm[i+1]>bm[i]+1)
                    bm[i+1]=bm[i]+1,flag=1;
            for(int i=maxV-1;   i>=minV;    i--)
                if(bm[i]>bm[i+1])
                    bm[i]=bm[i+1],flag=1;
        }
        printf("%d\n",bm[maxV]-bm[minV]);
    }
    return 0;
}