Is the Information Reliable? Description
The galaxy war between the Empire Draco and the Commonwealth of Zibu broke out 3 years ago. Draco established a line of defense called Grot. Grot is a straight line with N defense stations. Because of the cooperation of the stations, Zibu’s Marine Glory cannot march any further but stay outside the line.
A mystery Information Group X benefits form selling information to both sides of the war. Today you the administrator of Zibu’s Intelligence Department got a piece of information about Grot’s defense stations’ arrangement from Information Group X. Your task is to determine whether the information is reliable.
The information consists of M tips. Each tip is either precise or vague.
Precise tip is in the form of P A B X, means defense station A is X light-years north of defense station B.
Vague tip is in the form of V A B, means defense station A is in the north of defense station B, at least 1 light-year, but the precise distance is unknown.
Input
There are several test cases in the input. Each test case starts with two integers N (0 < N ≤ 1000) and M (1 ≤ M ≤ 100000).The next M line each describe a tip, either in precise form or vague form.
Output
Output one line for each test case in the input. Output “Reliable” if It is possible to arrange N defense stations satisfying all the M tips, otherwise output “Unreliable”.
Sample Input
3 4 P 1 2 1 P 2 3 1 V 1 3 P 1 3 1 5 5 V 1 2 V 2 3 V 3 4 V 4 5 V 3 5 Sample Output
Unreliable Reliable Source
POJ Monthly–2006.08.27, Dagger
题意： 有n个防御站点，南北方向上形成一条直线。现在有m条信息，信息有两种，准确信息P A B x 表示 A 在 B 北 x 光年处，和模糊信息V A B 表示A 在B的北面 。问是否可以根据这些信息安排防御站点（是否存在矛盾关系）？
分析： 这是标准的差分约束系统的题目。关系差分约束系统 大家可以看看这 http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html 讲的非常的好！！！ 对于本题： 1.P A B X -> A - B == X -> A - B <= X && B - A <= -X 2.V A B -> A - B >= 1 -> B - A <= -1 然后建图后判断最短路中是否有负环即可。由于没有固定的起点，所以我们可以构造一个超级源点S
AC代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <cmath> using namespace std; const int INF = 0xffffff; const int maxm = 300000; const int maxn = 1010; int n,m,e; struct Edge { int u,v,w,next; Edge(){}; Edge(int u_,int v_,int w_) { u = u_; v = v_; w = w_; } }edges[maxm]; int head[maxn],d[maxn],cnt[maxn]; bool inq[maxn]; void addedges(int u,int v,int w) { edges[e] = Edge(u,v,w); edges[e].next = head[u]; head[u] = e++; } void spfa() { queue<int> q; while(!q.empty()) q.pop(); memset(inq,false,sizeof(inq)); memset(cnt,0,sizeof(cnt)); for(int i=1;i<=n;i++) d[i] = INF; d[0] = 0; inq[0] = true; cnt[0] = 1; q.push(0); while(!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for(int i=head[u];i!=-1;i=edges[i].next) { int v = edges[i].v; if(d[v] > d[u] + edges[i].w) { d[v] = d[u] + edges[i].w; if(!inq[v]) { inq[v] = true; q.push(v); cnt[v]++; if(cnt[v] > n) { printf("Unreliable\n"); return; } } } } } printf("Reliable\n"); } int main() { int u,v,w; char s; while(scanf("%d%d\n",&n,&m)!=EOF) { e = 0; memset(head,-1,sizeof(head)); for(int i=0;i<m;i++) { scanf("%c",&s); if(s == 'P') { scanf("%d%d%d",&u,&v,&w); addedges(v,u,w); addedges(u,v,-w); } else { scanf("%d%d",&u,&v); addedges(u,v,-1); } getchar(); } int s = 0;//源点 for(int i=1;i<=n;i++) addedges(s,i,0); spfa(); } return 0; }