poj 2983 Is the Information Reliable? (差分约束)

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

Sample Output

Unreliable
Reliable

Source

POJ Monthly--2006.08.27, 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<stdio.h>
 3 #include<string.h>
 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<n;i++){
21         int flag=1;
22         for(int j=0;j<edgenum;j++){
23             if(d[edge[j].u]!=inf && d[edge[j].v]>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<edgenum;j++)
31         if(d[edge[j].u]!=inf && d[edge[j].v]>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<m;i++){
43             getchar();
44             scanf("%c",&op);
45             if(op=='P'){
46                 scanf("%d%d%d",&a,&b,&c);
47                 addedge(a,b,-c);
48                 addedge(b,a,c);
49             }else{
50                 scanf("%d%d",&a,&b);
51                 addedge(a,b,-1);
52             }
53         }
54         if(bellman_ford()) puts("Reliable");
55         else puts("Unreliable");
56     }
57     return 0;
58 }

View Code

spfa

 1 //Accepted    2704K    704MS    C++    1641B    2013-11-29 09:18:36
 2 #include<iostream>
 3 #include<queue>
 4 #include<vector>
 5 #include<stdio.h>
 6 #include<string.h>
 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<node>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<int>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<n0;i++){
35             int v=V[u][i].v;
36             int w=V[u][i].w;
37             if(d[v]>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<m;i++){
59             scanf("%c",&op);
60             if(op=='P'){
61                 scanf("%d%d%d",&a,&b,&c);
62                 V[a].push_back(node(b,-c));
63                 V[b].push_back(node(a,c));
64             }else{
65                 scanf("%d%d",&a,&b);
66                 V[a].push_back(node(b,-1));
67             }
68             getchar();
69         }
70         if(spfa()) puts("Reliable");
71         else puts("Unreliable");
72     }
73     return 0;
74 }

View Code