图论--差分约束--POJ 2983--Is the Information Reliable?
图论--差分约束--POJ 2983--Is the Information Reliable?
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 Reliabl 给出了 P a b w 表示 b在a以北w公里， V a b 表示 b在a北边，最少1公里，问所有 的条件可不可以全部满足。
由P 可以得到 b - a = w 也就是b - a <= w && a - b <= w ，由 V a b 得到 b - a >= 1 也就是 a - b <= -1 ;建图，使用最短路，判断是否会有负环。初始dis要全部为0.
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=1000+10;
const int maxm=100000*3;
struct Edge
{
int from,to,dist;
Edge(){}
Edge(int f,int t,int d):from(f),to(t),dist(d){}
};
struct BellmanFord
{
int n,m;
int head[maxn],next[maxm];
Edge edges[maxm];
int d[maxn];
int cnt[maxn];
bool inq[maxn];
void init(int n)
{
this->n=n;
m=0;
memset(head,-1,sizeof(head));
}
void AddEdge(int from,int to,int dist)
{
edges[m]=Edge(from,to,dist);
next[m]=head[from];
head[from]=m++;
}
bool bellman_ford()
{
memset(inq,0,sizeof(inq));
memset(cnt,0,sizeof(cnt));
queue<int> Q;
for(int i=0;i<n;i++) d[i]= i==0?0:INF;
Q.push(0);
while(!Q.empty())
{
int u=Q.front(); Q.pop();
inq[u]=false;
for(int i=head[u];i!=-1;i=next[i])
{
Edge &e=edges[i];
if(d[e.to] > d[u]+e.dist)
{
d[e.to] = d[u]+e.dist;
if(!inq[e.to])
{
inq[e.to]=true;
Q.push(e.to);
if(++cnt[e.to]>n) return true;
}
}
}
}
return false;
}
}BF;
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)==2)
{
BF.init(n+1);
while(m--)
{
char s[10];
int u,v,d;
scanf("%s",s);
if(s[0]=='P')
{
scanf("%d%d%d",&u,&v,&d);
BF.AddEdge(u,v,d);
BF.AddEdge(v,u,-d);
}
else if(s[0]=='V')
{
scanf("%d%d",&u,&v);
BF.AddEdge(v,u,-1);
}
}
for(int i=1;i<=n;i++)
BF.AddEdge(0,i,0);
printf("%s\n",BF.bellman_ford()?"Unreliable":"Reliable");
}
return 0;
}腾讯云开发者
