[差分约束]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",&amp;a,&amp;b,&amp;c);
                addedge(b,a,c);
                addedge(a,b,-c);
            }
            else{
                scanf("%d%d",&amp;a,&amp;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;
}