【POJ 2983】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 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 Reliable
Source
建立差分约束系统进行求解
存在两种关系
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 <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#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 <int> 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;
}