题目链接: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;
}