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;
}