POJ - 3169 SPFA解差分约束除了有解,负环还有另一种情况

题意就是有N头牛排成一个直线..有些牛之间互相讨厌..距离必须大于等于某个...有些牛之间相互暧昧..距离必须小于等于某个...牛的前后顺序和编号是一样的...问这些牛最多能排多长..

比较传统的SPFA解差分约束..但值得注意的是这里出现了除了有解负环还有另一种情况...那就是值不确定...如给出

4 1 0

1 2 1

这时那 3 4 的值根本无从确定...在SPFA过程中的体现是 d [ ] 值是初始的值没有更新...

ps: 刚才看到一句话很好..:

求最大值，做最短路径

求最小值，做最长路径

Program:

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<queue>
#define ok printf("ok!!\n")
#define MAXN 1001
#define oo 0x7F
using namespace std;
struct p1
{
    int x,y,k,next;
}line[MAXN*31];
int n,m,ml,md,p,x,y,k,i,link[MAXN],h,d[MAXN],sum[MAXN];
bool used[MAXN];
queue<int> myqueue;
int SPFA()
{  
    while (!myqueue.empty()) myqueue.pop();
    memset(d,oo,sizeof(d));
    memset(used,false,sizeof(used));
    memset(sum,0,sizeof(sum));
    myqueue.push(1); d[1]=0; sum[1]=1;
    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;
                    sum[line[k].y]++;
                    if (sum[line[k].y]>n) return -1;
                    myqueue.push(line[k].y);
                }
            }
            k=line[k].next;
        }
    }
    if (d[n]==2139062143) return -2;
    return d[n];
}
int main()
{ 
    while (~scanf("%d%d%d",&n,&ml,&md))
    {
         memset(line,0,sizeof(line));
         memset(link,0,sizeof(link));
         m=0;
         while (ml--)
         {
             scanf("%d%d%d",&x,&y,&k);  
             m++;
             line[m].x=x; line[m].y=y; line[m].k=k;
             line[m].next=link[line[m].x];
             link[line[m].x]=m;
         }
         while (md--)
         {
             scanf("%d%d%d",&x,&y,&k); 
             m++;
             line[m].x=y; line[m].y=x; line[m].k=-k;
             line[m].next=link[line[m].x];
             link[line[m].x]=m;               
         }
         for (i=1;i<n;i++)
         {
             m++;    
             line[m].x=i+1; line[m].y=i; line[m].k=0;
             line[m].next=link[line[m].x];
             link[line[m].x]=m;              
         } 
         printf("%d\n",SPFA());
    }
    return 0;
}