加载中...

POJ 2983 - Is the Information Reliable?


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;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
赏
  目录