题目地址:POJ 2983

题意：有N个车站。给出一些点的精确信息和模糊信息。精确信息给出两点的位置和距离。模糊信息给出两点的位置。但距离大于等于一。试确定是否全部的信息满足条件。

思路：事实上就是让你推断是否存在负环。好久才看明确。对于精确消息。能够得出两个差分公式:dis[v] <= dist[u] - w  &&  dist[u] <= dist[v] + w。对于模糊信息。能够得出dis[v] <= dis[u] -1。

PS:做差分约束感觉还是Bellman_ford好用啊。

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <sstream>

#include <algorithm>

#include <set>

#include <queue>

#include <stack>

#include <map>

using namespace std;

typedef long long LL;

const int inf=0x3f3f3f3f;

const double pi= acos(-1.0);

const double esp=1e-6;

const int maxn=2010;

int dis[maxn],head[2010];

int cnt;

struct node

{

    int u,v,w;

    int next;

}edge[1000010];

void add(int u,int v,int w)

{

    edge[cnt].u=u;

    edge[cnt].v=v;

    edge[cnt].w=w;

    edge[cnt].next=head[u];

    head[u]=cnt++;

}

int Bellman_ford(int n)

{

    int i,j;

    memset(dis,inf,sizeof(dis));

    dis[1]=0;

    for(i=1;i<=n;i++){

        int flag=0;

        for(j=0;j<cnt;j++){

            int u=edge[j].u;

            int v=edge[j].v;

            if(dis[v]>dis[u]+edge[j].w){

                dis[v]=dis[u]+edge[j].w;

                flag=1;

            }

        }

        if(!flag) break;

    }

    for(i=0;i<cnt;i++){

        if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)

            return 0;

    }

    return 1;

}

int main()

{

    int n,m,i;

    int u,v,w;

    char str;

    while(~scanf("%d %d",&n,&m)){

        memset(head,-1,sizeof(head));

        cnt=0;

        while(m--){

            getchar();

            scanf("%c",&str);

            if(str=='P'){

                scanf("%d %d %d",&u,&v,&w);

                add(u,v,w);

                add(v,u,-w);

            }

            else{

                scanf("%d %d",&u,&v);

                add(v,u,-1);

            }

        }

        int ans=Bellman_ford(n);

        if(ans)

            puts("Reliable");

        else

            puts("Unreliable");

    }

    return 0;

}