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

2017年11月9日 0 条评论 16 次阅读 0 人点赞

题目链接:POJ - 2983

题目大意:

有部分点之间知道具体相对位置,

有部分点仅知道一点在另一点的某边。

问是否存在这样的点集。

题目分析:

建图,差分约束系统。

注意的是,对于spfa(),要加入一个权为0的超级源点,使得图连通。

bellman-ford算法则不需要。

给出代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;
#define ll long long int;
const int maxn=300000+10;
const int maxs=2000+10;
const int inf=0x3f3f3f3f;
int head[maxn];
struct edge
{
    int from;
    int to;
    int next;
    int val;
} edges[maxn];
int cnt;
void push_edge(int from,int to,int val)
{
    edges[cnt].from=from;
    edges[cnt].to=to;
    edges[cnt].val=val;
    edges[cnt].next=head[from];
    head[from]=cnt++;
}
void init()
{
    cnt=0;
    memset(head,-1,sizeof(head));
}
int n,m;
int dis[maxs];
bool bell_ford(int s)
{
    memset(dis,inf,sizeof(inf));
    dis[1]=0;
    for(int i=1;i<=n;i++)
    {
        int flag=1;
        for(int j=0;j<cnt;j++)
        {
            if(dis[edges[j].to]>dis[edges[j].from]+edges[j].val)
            {
                dis[edges[j].to]=dis[edges[j].from]+edges[j].val;
                flag=0;
            }
        }
        if(flag)
            break;
    }
    for(int i=0; i<cnt; i++)
    {
        if(dis[edges[i].to]>dis[edges[i].from]+edges[i].val)
            return false;
    }
    return true;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        int flag=1;
        for(int i=0; i<m; i++)
        {
            //cout<<i<<" "<<m<<endl;
            string s;
            cin>>s;
            if(s[0]=='P')
            {
                int a,b,c;
                scanf("%d%d%d",&a,&b,&c);
                if(a==b&&c!=0)
                    flag=0;
                push_edge(b,a,-c);
                push_edge(a,b,c);
            }
            else
            {
                int a,b;
                scanf("%d%d",&a,&b);
                if(a==b)
                    flag=0;
                push_edge(b,a,-1);
            }
        }
        if(bell_ford(n))
            cout<<"Reliable"<<endl;
        else
            cout<<"Unreliable"<<endl;
    }
    return 0;
}

DLKKILL

这个人太懒什么东西都没留下

文章评论(0)