POJ-1716 同上..SPFA差分约束..

   题意和POJ1201相似..但更简单..就是说 a 到 b 至少有两个数...问整个集合最少需要多少元素...

   约束条件也就是 Sb - S(a-1) >=2...同POJ1201的构图和解法就是了...

Program :

#include<iostream>
#include<queue>
#define oo 0x7F
#define MAXN 30001
using namespace std;
struct p1
{
int x,y,k,next;
}line[MAXN];
int n,m,link[MAXN],x,y,minnum,maxnum,i;
queue<int> myqueue;
int SPFA()
{
int i,k,h,d[MAXN];
bool used[MAXN];
while (!myqueue.empty()) myqueue.pop();
memset(d,-oo,sizeof(d));
memset(used,false,sizeof(used));
d[minnum]=0; myqueue.push(minnum);
while (!myqueue.empty())
{
h=myqueue.front();
myqueue.pop();
used[h]=false;
k=link[h];
while (k)
{
if (d[line[k].y]<d[h]+line[k].k)
{
d[line[k].y]=d[h]+line[k].k;
if (!used[line[k].y])
{
used[line[k].y]=true;
myqueue.push(line[k].y);
}
}
k=line[k].next;
}
}
return d[maxnum];
}
int main()
{
while(~scanf("%d",&n))
{
m=0;
memset(link,0,sizeof(link));
memset(line,0,sizeof(line));
minnum=oo; maxnum=-oo;
while (n--)
{
scanf("%d%d",&x,&y);
y++;
if (x<minnum) minnum=x;
if (y>maxnum) maxnum=y;
m++;
line[m].x=x; line[m].y=y; line[m].k=2;
line[m].next=link[line[m].x];
link[line[m].x]=m;
}
for (i=minnum;i<maxnum;i++)
{
m++;
line[m].x=i+1; line[m].y=i; line[m].k=-1;
line[m].next=link[line[m].x];
link[line[m].x]=m;
m++;
line[m].x=i; line[m].y=i+1; line[m].k=0;
line[m].next=link[line[m].x];
link[line[m].x]=m;
}
printf("%d\n",SPFA());
}
return 0;
}