传送门

描述

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.

输入

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 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”.

样例

• 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
• Output
  Unreliable
  Reliable

思路

• 题意：一天南北线上有n个防御站，给出他们之间的位置关系，问有没有可能存在这样一种位置布置符合所给的位置关系。关系有两种，一种是 P A B X，表示A在B北边X光年的位置，V A B表示A在B北边至少1光年位置。
• 若出现负环则不满足情况，求最长路最短路都可以，这里用最长路
• 用vis数组存下每个点的访问次数，如果>=n,则必有负环
• 对P：B-A=X => B-A>=x&&B-A<=x,所以建两条边B A -X和 A B X;
  对V：B-A>=1，建边 A B 1；
  另外，对所有的点，i-0>=0，建边 0 i 0；
• spfa 链式向前星

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

#include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #define INIT(a,b) memset(a,b,sizeof(a)) #define LL long long int using namespace std; const int MAX=0x7fffffff; const int MIN=-0x7fffffff; const int INF=0x3f3f3f3f; const int Mod=1e9+7; const int maxn=1007; int n,m,Begin[maxn],used[maxn],dis[maxn],vis[maxn]; struct Node{ int To,Dis,Next;}; Node Edge[1000007];int top=0; void add(int x,int y,int w){ Edge[top]=(Node){y,w,Begin[x]}; Begin[x]=top++; } bool spfa(int t){ INIT(vis,0);INIT(used,0);INIT(dis,-1);dis[t]=0; queue
                
                 lroad; lroad.push(t);used[t]=1;vis[t]++; while(!lroad.empty()){ int now=lroad.front();used[now]=0;lroad.pop(); for(int i=Begin[now];~i;i=Edge[i].Next){ int tem=Edge[i].To; if(dis[tem]
                 
                  =n)return false; used[tem]=1; lroad.push(tem); } } } } return true; } int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); while(~scanf("%d%d",&n,&m)){ INIT(Begin,-1);top=0; char s;int a,b,c; while(m--){ getchar(); scanf("%c",&s); if(s=='P'){ scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,-c); } else if(s=='V'){ scanf("%d%d",&a,&b); add(a,b,1); } } for(int i=0;i