【POJ 2983】Is the Information Reliable?（差分约束系统）-白红宇

【POJ 2983】Is the Information Reliable?（差分约束系统）

阅读量：6307 次

发布时间：2019-06-22

本文共 3262 字，大约阅读时间需要 10 分钟。

（差分约束系统）

Is the Information Reliable?

Time Limit: 3000MS		Memory Limit: 131072K
Total Submissions: 12244		Accepted: 3861

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

建立差分约束系统进行求解

存在两种关系

P a b x 表示a在b北边x光年等价与Pb - Pa = x

想要表示等于就要转换成 Pb - Pa >= x Pb - Pa <= x

即为 Pb-Pa >= x Pa - Pb >= -x

V a b 表示a在b北边至少一光年即为Pb - Pa >= 1

用三个公式建立差分约束系统就可以因为可能是多个不连通图就须要用一个超级源点把他们都链接起来

假设跑最短的过程中没有负环即说明是合法的关系图否则Unreliable

代码例如以下:

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define LL long long#define fread() freopen("in.in","r",stdin)#define fwrite() freopen("out.out","w",stdout)using namespace std;const int INF = 0x3f3f3f3f;const int msz = 10000;const double eps = 1e-8;int dcmp(double x){ return x < -eps? -1: x > eps;}struct Edge{ int v,w,next;};Edge eg[233333];int head[1010];int dis[1010];int cnt[1010];bool vis[1010];int n,m,tp;void Add(int u,int v,int w){ eg[tp].v = v; eg[tp].w = w; eg[tp].next = head[u]; head[u] = tp++;}bool SPFA(){ memset(dis,-INF,sizeof(dis)); memset(cnt,0,sizeof(cnt)); memset(vis,0,sizeof(vis)); vis[0] = 1; dis[0] = 0; cnt[0]++; queue 
                
                  q; q.push(0); int u,v,w; while(!q.empty()) { u = q.front(); vis[u] = 0; q.pop(); for(int i = head[u]; i != -1; i = eg[i].next) { v = eg[i].v; w = eg[i].w; if(dis[v] < dis[u]+w) { dis[v] = dis[u]+w; cnt[v]++; if(cnt[v] > n) return false; if(!vis[v]) { q.push(v); vis[v] = 1; } } } } return true;}int main(){ int u,v,w; char opt[3]; while(~scanf("%d%d",&n,&m)) { memset(head,-1,sizeof(head)); tp = 0; while(m--) { scanf("%s",opt); if(opt[0] == 'P') { scanf("%d%d%d",&u,&v,&w); Add(u,v,w); Add(v,u,-w); } else { scanf("%d%d",&u,&v); Add(u,v,1); } } for(int i = 1; i <= n; ++i) { Add(0,i,0); } puts(SPFA()? "Reliable": "Unreliable"); } return 0;}

转载地址：http://trnxa.baihongyu.com/

你可能感兴趣的文章