- POJ 2983 - Is the Information Reliable?
- Time: 3000MS
- Memory: 131072K
- 难度: 中级
- 分类: 差分约束
0x00 POJ 原题
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
POJ Monthly–2006.08.27, Dagger
0x10 题目概述
给出 M 个表达式,判断这些信息是否可靠。
0x20 解题思路
差分约束+Bellman-Ford(建议用优化的 Bellman-Ford)
设 dist[i] 为超级源点到 i 点的距离,则
建立 <= 的差分系统:
由于 P A B X 指“确定 A 到 B 的距离(边权)为 X”
从 P A B X 得到的差分系统为
dist[A] - dist[B] >= X && dist[A] - dist[B] <= X
等价于
dist[B] <= dist[A] - X && dist[A] <= dist[B] + X
则 if(dist[B] > dist[A]-X) 松弛:dist[B] = dist[A]-X
由于 V A B 指“只知道 A 到 B 的距离(边权)至少为 1”
从 V A B 得到的差分系统为
dist[A] >= dist[B] +1
等价于
dist[B] <= dist[A] -1
则 if(dist[B] > dist[A] -1) 松弛:dist[B] = dist[A] -1
注意:
- (1)建立
<=的差分系统,就必须求最短路(Bellman-Ford 算法)。而信息是否可靠,就是判断图中是否存在负权回路(也是利用 Bellman-Ford 判断) - (2)由于最坏有 10W 组不等式,经实测用
scanf输入比cin要节省 1500ms - (3)经实测用优化 Bellman-Ford 算法比普通 Bellman-Ford 算法快 2000ms
0x30 AC 源码
0x31 解题方法一:差分约束+优化 Bellman
/*差分约束+优化Bellman*/
//Memory Time
//2596K 485MS
#include <iostream>
using namespace std;
const int inf=1000000000;
class
{
public:
int s,e;
}edge[200001];
int N; //太空站数目
int M; //tips数
int dist[1001]; //源点到各点的距离
int w[200001]; //边权
int main(int i,int j)
{
while(cin>>N>>M)
{
memset(dist,0,sizeof(dist)); //初始化源点到各点的距离
int pe=0;
for(i=0;i<M;i++)
{
char pv;
int a,b,x;
getchar(); //吃掉回车
scanf("%c",&pv); //由于要频繁输入,用scanf比cin要快1500ms
if(pv=='P') //清晰边权,即A、B间距离确定,建立双向边
{
scanf("%d%d%d",&a,&b,&x);
edge[pe].s=a;
edge[pe].e=b;
w[pe++]=x;
edge[pe].s=b;
edge[pe].e=a;
w[pe++]=-x;
}
else if(pv=='V') //模糊边权,即A、B间距离不确定,建立单向边
{
scanf("%d%d",&a,&b);
edge[pe].s=a;
edge[pe].e=b;
w[pe++]=1;
}
}
/*Bellman-Ford*/
bool sign; //用于Bellman-Ford算法优化
for(j=0;j<N;j++)
{
sign=false;
for(i=0;i<pe;i++)
if(dist[ edge[i].e ] > dist[ edge[i].s ] - w[i])
{
dist[ edge[i].e ] = dist[ edge[i].s ] - w[i];
sign=true;
}
if(!sign)//若dist没有任何改变,则以后也不会改变,可以直接退出循环
break;
}//循环n次后若flag == false 说明有负权回路,或者权值矛盾
if(sign)
cout<<"Unreliable"<<endl; //存在负权环
else
cout<<"Reliable"<<endl; //不存在负权环
}
return 0;
}
0x32 解题方法二:差分约束+无优化 Bellman
/*差分约束+无优化Bellman*/
//Memory Time
//2596K 2438MS
#include<iostream>
using namespace std;
const int inf=1000000000;
class
{
public:
int s,e;
}edge[200001];
int N; //太空站数目
int M; //tips数
int dist[1001]; //源点到各点的距离
int w[200001]; //边权
int main(int i,int j)
{
while(cin>>N>>M)
{
memset(dist,0,sizeof(dist)); //初始化源点到各点的距离
int pe=0;
for(i=0;i<M;i++)
{
char pv;
int a,b,x;
getchar(); //吃掉回车
scanf("%c",&pv);
if(pv=='P') //清晰边权,即A、B间距离确定,建立双向边
{
scanf("%d%d%d",&a,&b,&x);
edge[pe].s=a;
edge[pe].e=b;
w[pe++]=x;
edge[pe].s=b;
edge[pe].e=a;
w[pe++]=-x;
}
else if(pv=='V') //模糊边权,即A、B间距离不确定,建立单向边
{
scanf("%d%d",&a,&b);
edge[pe].s=a;
edge[pe].e=b;
w[pe++]=1;
}
}
/*Bellman-Ford*/
/*Relax*/
for(j=0;j<N;j++)
for(i=0;i<pe;i++)
if(dist[ edge[i].e ] > dist[ edge[i].s ] - w[i])
dist[ edge[i].e ] = dist[ edge[i].s ] - w[i];
/*Judge the Negative Circle*/
bool sign=false;
for(i=0;i<pe;i++)
if(dist[ edge[i].e ] > dist[ edge[i].s ] - w[i])
{
sign=true;
break;
}
if(sign)
cout<<"Unreliable"<<endl; //存在负权环
else
cout<<"Reliable"<<endl; //不存在负权环
}
return 0;
}