Time Limit: 3000MS | Memory Limit: 131072K | |
Total Submissions: 11334 | Accepted: 3575 |
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
差分约束,这里建边有2种,第一种是d[v] >= d[u] + w[u, v],那么从u->v连一条边,第二种告诉你的是等式关系,所以建边要正方向建一条边,反方向建一条边(权值为正方向边权值的相反数)
#include <map> #include <set> #include <list> #include <stack> #include <vector> #include <queue> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 1010; const int M = 200010; const int inf = 0x3f3f3f3f; queue <int>qu; int tot, n, m; int head[N]; int num[N]; int dist[N]; int in_queue[N]; struct node { int weight; int next; int to; }edge[M]; void addedge(int from, int to, int weight) { edge[tot].weight = weight; edge[tot].to = to; edge[tot].next = head[from]; head[from] = tot++; } bool spfa(int v0) { memset (dist, inf, sizeof(dist) ); memset (in_queue, 0, sizeof(in_queue) ); dist[v0] = 0; in_queue[v0]++; while ( !qu.empty() ) { qu.pop(); } qu.push(v0); while ( !qu.empty() ) { int u = qu.front(); qu.pop(); for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if (dist[v] > dist[u] + edge[i].weight) { dist[v] = dist[u] + edge[i].weight; in_queue[v]++; if (in_queue[v] == n + 1) { return false; } qu.push(v); } } } return true; } int main() { while (~scanf("%d%d", &n, &m)) { memset (head, -1, sizeof(head) ); tot = 0; char str[10]; int u, v, w; while (m--) { scanf("%s", str); if (str[0] == 'P') { scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); addedge(v, u, -w); } else { scanf("%d%d", &u, &v); addedge(v, u, -1); } } for (int i = 1; i <= n; ++i) { addedge(0, i, 0); } bool falg = spfa(0); if (falg) { printf("Reliable\n"); continue; } printf("Unreliable\n"); } return 0; }