题意就是有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 0x7Fusing 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;}
如果觉得《POJ - 3169 SPFA解差分约束除了有解 负环还有另一种情况》对你有帮助，请点赞、收藏，并留下你的观点哦！
