[差分约束]poj 2983：Is the Information Reliable?
大致题意：
? ? 给出n个点的m条约束信息。每条信息表述为(P a b c)表示a在b北方距离c的位置，或者(V a b) 表示a在b北方1单位距离或者更远的位置。问是否可能存在符合以上m个要求的点。
大致思路：
? ? 把dis[i]设为其到始点的距离。第二个条件很简单dis[a]-dis[b]>=1 也就是dis[b]<=dis[a]-1。对于第一个，带等于号的条件dis[a]-dis[b]==c，我们可以转化为dis[a]-dis[b]>=c和dis[a]-dis[b]<=c 两个不等式，然后再转化为最短路三角不等式。由于所有点不一定互相连通，所以要设一个虚拟始点，与所有点相连，长度设为0。然后用spfa来判定是否有可行解即可~
? ? 擦擦擦，我用了大半年的spfa队列模版居然有bug，找了一夜bug才ac掉。真心草~泥~马了
#include<iostream>#include<cmath>#include<cstdio>#include<cstring>using namespace std;const int nMax=200050;const int mMax=1000050;const int inf=1<<28;struct{ int u,v, next; int w;}edge[mMax];int n, k, head[nMax];int dis[nMax];int que[nMax],m,sum[nMax];bool vis[nMax];void addedge(int a,int b,int w){ edge[k].w = w; edge[k].u=a; edge[k].v=b; edge[k].next=head[a]; head[a]=k;k++;}bool spfa(int s){ //始点，终点，总点数 int i, hhead = 0, tail = 1; // 长注释的地方就是从最小费用改到最大费用时需要变动的地方 for(i = 0; i <= n; i ++){ dis[i] = inf;//////////// vis[i] = false; } dis[s] = 0; que[0] = s; vis[s] = true; while(tail != hhead){ // 循环队列实现。 int u = que[hhead]; vis[u] = false; for(int p = head[u]; p != 0; p = edge[p].next){ int v = edge[p].v; // 写成了edge[k].v，WA了一晚。 if(dis[v] > dis[u] + edge[p].w){ dis[v] = dis[u] + edge[p].w; if(!vis[v]){ vis[v] = true; que[tail ++] = v; if(tail == nMax) tail = 0; if(++sum[v] > n) return false; // 不包含初始的进栈。 } } } hhead ++; if(hhead == nMax) hhead = 0; } return 1;}int main(){ int m,i,j,a,b,c,s; char str[20]; while(cin>>n>>m){ s=0; k=1; memset(sum,0,sizeof(sum)); memset(head,0,sizeof(head)); while(m--){ scanf("%s",str); if(str[0]=='P'){ scanf("%d%d%d",&a,&b,&c); addedge(b,a,c); addedge(a,b,-c); } else{ scanf("%d%d",&a,&b); addedge(a,b,-1); } } for(i=1;i<=n;i++){ addedge(s,i,0); } if (spfa(s)) printf("Reliable\n"); else printf("Unreliable\n"); } return 0;}?
??