Is the Information Reliable?

Time Limit: 3000MS		Memory Limit: 131072K
Total Submissions: 10303		Accepted: 3204

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 4P 1 2 1P 2 3 1V 1 3P 1 3 15 5V 1 2V 2 3V 3 4V 4 5V 3 5

Sample Output

UnreliableReliable

Source

, Dagger

 

题意：

        给定n个变量，m组不等式，求解。

       其中P操作表示权值为X的双向变，V操作表示权值为1的单向边。

 

差分约束：

       其实看到这类题就应该想到是差分约束。因为做得还不多，了解还不是很深，构图时出现麻烦，WA了很多次。

       这题也是要用到求最短路的算法，但是不用求最短路，只要求是否存在负权环，建图模型为：

      bellman_ford:

                 P: g[a][b]=-x, 

                     g[b][a]=x;

                 V:g[a][b]=1;

      spfa:

                此方法要在bellman的基础上加上

                                for i=0 ... n do  

                                         g[0][i]=0;

照旧给出两种方法的代码：

     bellman_ford:

1 //Accepted    2488K    485MS    C++    1315B    2013-11-29 09:33:23 2 #include
      
        3 #include
       
         4 #define N 1005 5 #define inf 0x7ffffff 6 struct node{ 7     int u,v,w; 8 }edge[400005]; 9 int d[N];10 int n,m,edgenum;11 void addedge(int u,int v,int w)12 {13     edge[edgenum].u=u;14     edge[edgenum].v=v;15     edge[edgenum++].w=w;16 }17 bool bellman_ford()18 {19     memset(d,0,sizeof(d));20     for(int i=0;i
        
         d[edge[j].u]+edge[j].w){24                 d[edge[j].v]=d[edge[j].u]+edge[j].w;25                 flag=0;26             }27         }28         if(flag) break;29     }30     for(int j=0;j
         
          d[edge[j].u]+edge[j].w)32             return 0;33     return 1;34 }35 int main(void)36 {37     char op;38     int a,b,c;39     while(scanf("%d%d",&n,&m)!=EOF)40     {41         edgenum=0;42         for(int i=0;i
         
        
       
      

 

     spfa

1 //Accepted    2704K    704MS    C++    1641B    2013-11-29 09:18:36 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #define inf 0x7ffffff 8 #define N 1005 9 using namespace std;10 struct node{11     int v,w;12     node(int a,int b){13         v=a;w=b;14     }15 };16 vector
           
            V[N];17 int vis[N];18 int d[N];19 int n,m;20 bool spfa()21 {22 int in[N]={ 0};23 memset(vis,0,sizeof(vis));24 for(int i=0;i<=n;i++) d[i]=inf;25 queue
            
             Q;26 d[0]=0;27 Q.push(0);28 while(!Q.empty()){29 int u=Q.front();30 Q.pop();31 if(in[u]>=n) return false;32 vis[u]=0;33 int n0=V[u].size();34 for(int i=0;i
             
              d[u]+w){38 d[v]=d[u]+w;39 in[v]++; 40 if(!vis[v]){41 Q.push(v);42 vis[v]=1;43 } 44 } 45 } 46 }47 return true;48 }49 int main(void)50 {51 char op;52 int a,b,c;53 while(scanf("%d%d%*c",&n,&m)!=EOF)54 {55 for(int i=0;i<=n;i++) V[i].clear();56 for(int i=0;i<=n;i++)57 V[0].push_back(node(i,0));58 for(int i=0;i