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

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

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

题意:

有N个防御站排成一条竖线放置.现在有M个条件,问你该防御系统是否可能满足所有M个条件.这M个条件形似如下:

P A B X ,表示A在B的北面X光年处.

V A B ,表示A在B的北面至少1光年处.

现在要你判断是否存在可行的系统?

分析:

首先我们令d[i]表示最北方离i号防御站的距离.

所以对于P A B X的条件可以推出: d[A] + X= d[B].(等价于d[A] <= d[B]-X 且 d[B]<=d[A]+X) 根据差分约束系统,我们可以添加对应的边为: B到A权值-X的边, A到B权值X的边.

对于V A B条件可以推出: d[A] <= d[B]-1. 可以添加对应的边为: B到A 的权值为-1的边.

所有点的最短距离d[i]都置为INF,且0号点(超级源)的初始d设为0.然后求从0号点到其他所有点的最短距离并用BellmanFord算法来判断是否存在负权环即可. 因为本题需要判断是否存在可行方案,所以只能用POJ1201中提到的方案1.

(POJ1201:http://blog.csdn.net/u013480600/article/details/37922977 )

AC代码:

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=1000+10;
const int maxm=100000*3;
struct Edge
{
    int from,to,dist;
    Edge(){}
    Edge(int f,int t,int d):from(f),to(t),dist(d){}
};

struct BellmanFord
{
    int n,m;
    int head[maxn],next[maxm];
    Edge edges[maxm];
    int d[maxn];
    int cnt[maxn];
    bool inq[maxn];

    void init(int n)
    {
        this->n=n;
        m=0;
        memset(head,-1,sizeof(head));
    }

    void AddEdge(int from,int to,int dist)
    {
        edges[m]=Edge(from,to,dist);
        next[m]=head[from];
        head[from]=m++;
    }

    bool bellman_ford()
    {
        memset(inq,0,sizeof(inq));
        memset(cnt,0,sizeof(cnt));
        queue<int> Q;
        for(int i=0;i<n;i++) d[i]= i==0?0:INF;
        Q.push(0);

        while(!Q.empty())
        {
            int u=Q.front(); Q.pop();
            inq[u]=false;
            for(int i=head[u];i!=-1;i=next[i])
            {
                Edge &e=edges[i];
                if(d[e.to] > d[u]+e.dist)
                {
                    d[e.to] = d[u]+e.dist;
                    if(!inq[e.to])
                    {
                        inq[e.to]=true;
                        Q.push(e.to);
                        if(++cnt[e.to]>n) return true;
                    }
                }
            }
        }
        return false;
    }
}BF;

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        BF.init(n+1);
        while(m--)
        {
            char s[10];
            int u,v,d;
            scanf("%s",s);
            if(s[0]=='P')
            {
                scanf("%d%d%d",&u,&v,&d);
                BF.AddEdge(u,v,d);
                BF.AddEdge(v,u,-d);
            }
            else if(s[0]=='V')
            {
                scanf("%d%d",&u,&v);
                BF.AddEdge(v,u,-1);
            }
        }
        for(int i=1;i<=n;i++)
            BF.AddEdge(0,i,0);
        printf("%s\n",BF.bellman_ford()?"Unreliable":"Reliable");
    }
    return 0;
}