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
这是一道最短路差分约束题,通俗一点讲就是给你一些表达试看是不是可靠,就是存在不存在矛盾。
这里的P A B X可以转化为A-B<=X或B-A>=X
V A B,则可以转化为A-B<=-1
对于《=的差分约束题,就要用到最短路,而判断信息的可靠与否就要判断图中是否存在负权回路即环。
代码:
分享到:
相关推荐
北大POJ3414-Pots 解题报告+AC代码
poj3045的源码,很久以前写的,语言是C++
poj 2820 古代密码 http://poj.grids.cn/problem?id=2820 可直接运行
poj2880 输入一个英文句子,长度不超过40个字符。编写程序,输出句子中最长的一个单词。 http://poj.grids.cn/problem?id=2880 可直接运行
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够...
经典的0-1背包问题. 适合新手学习. 原题网址:http://poj.grids.cn/problem?id=2773
poj1691解题报告 题目来源:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691) 解法: 搜索
//http://poj.org/problem?id=1611 #include using namespace std; const int maxn = 30010; int f[maxn],num[maxn],n,m; int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); } int main() { while(cin...
如输入数据为 3 11011000 输出为 IIIBIFFIBFBBBFF 第4题(http://poj.org/problem?id=1050) To the Max Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 25250 Accepted: 13051 Description Given a ...
POJ problems ID Problem C++ 1001 1002 1003 1004 1006 1007 专题分类 (一)简单搜索 ID Problem C++ Source 1 HDU 2553 (精简版) 2 HDU 1312 3 POJ 3984 4 POJ 2251 5 POJ 3278 6 POJ 3279 7 ZOJ 1002 8 POJ 1321 9...
POJ problems ID Problem C++ 1001 1002 1003 1004 1006 1007 专题分类 (一)简单搜索 ID Problem C++ Source 1 HDU 2553 (精简版) 2 HDU 1312 3 POJ 3984 4 POJ 2251 5 POJ 3278 6 POJ 3279 7 ZOJ 1002 8 POJ 1321 9...