POJ 2983 Is the Information Reliable?(差分约束系统)

http://poj.org/problem?id=2983

题意:N 个 defense stations,M条消息,消息有精确和模糊之分,若前边为P。则为精确消息,有两个defense stations和他们之间的距离,若为P A B X 则是精确消息,并且A在B北边X光年远,V A B则是模糊消息,A在B北边,不知道距离,但至少是1光年远。

思路 :这个题要转化成差分约束。因为dist[a]-dist[b] = x,所以转化成差分约束x<=dist[a]-dist[b]<=x ,模糊消息因为至少为1,所以转化后为 dist[b] - dist[a] >= 1,化简之后为 dist[b] - dist[a] <= x    dist[a] - dist[b] <= -x    dist[a] - dist[b]  <= -1.

POJ 2983 Is the Information Reliable?(差分约束系统)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>

using namespace std ;
const int INF = 99999999 ;
int cnt,m ,n;
int dist[15010] ;//源点到各点的距离

struct node
{
    int u,v,w ;
}edge[10700700] ;

void addedge(int u,int v,int w)//加边
{
    edge[cnt].u = u ;
    edge[cnt].v = v ;
    edge[cnt].w = w ;
    cnt++ ;
}

bool bellman_ford(int start)
{
    for(int i = 1 ; i <= n ; i++)
    i == start ? dist[i] = 0 : dist[i] = INF ;
    for(int i = 1 ; i < n ; i++)
    {
        bool flag = false ;
        for(int j = 0 ; j < cnt ; j++)
        {
            int u = edge[j].u,v = edge[j].v,w = edge[j].w ;
            if(dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w ;
                flag = true ;
            }
        }
        if(!flag)//若dist没有任何改变说明以后也不会变,可直接返回
        return true ;
    }  
    for(int j = 0 ; j < cnt ; j++)
    {
        int u = edge[j].u,v = edge[j].v,w = edge[j].w ;
        if(dist[v] > dist[u] + w)
        return false ;
    }
    return true ;
}

int main()
{
    char ch ;
    int u,v,w ;
    while(~scanf("%d %d",&n,&m))
    {
        cnt = 0 ;
        for(int i = 0 ; i < m ; i++)
        {
            getchar() ;
            scanf("%c",&ch) ;
            if(ch == P)
            {
                scanf("%d %d %d",&u,&v ,&w) ;//两点距离确定建立双向边
                addedge(v,u,-w) ;
                addedge(u,v,w) ;
            }
            if(ch == V)
            {
                scanf("%d %d",&u,&v) ;//两点距离不定,建立单向边
                addedge(v,u,-1) ;
            }
        }
        if(bellman_ford(1))
        printf("Reliable\n") ;
        else printf("Unreliable\n") ;
    }
    return 0 ;
}
View Code

POJ 2983 Is the Information Reliable?(差分约束系统)

上一篇:架构师给程序员的一封信


下一篇:JAVA基础学习之 Map集合、集合框架工具类Collections,Arrays、可变参数、List和Set集合框架什么时候使用等(4)