POJ 3169 Layout(差分约束系统)

POJ 3169 Layout(差分约束系统)

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

题意:

当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。FJ有N（2<=N<=1000）头奶牛，编号从1到N，沿一条直线站着等候喂食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上。即使说，如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。

一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数L。另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数D。给出ML条关于两头奶牛间有好感的描述，再给出MD条关于两头奶牛间存有反感的描述。（1<=ML,MD<=10000，1<=L,D<=1000000）

你的工作是：如果不存在满足要求的方案，输出-1；如果1号奶牛和N号

奶牛间的距离可以任意大，输出-2；否则，计算出在满足所有要求的情况下，1号奶牛和N号奶牛间可能的最大距离。

分析:

假设奶牛按自己的编号1到N在一条直线上从左往右排队.我们令s[i]表示第i头奶牛距离最左端的距离.

因为奶牛要按他们的编号从左到右排列,所以必然有s[i]-s[i-1]>=0条件.另外对于ML条好感条件如 i j k(由题意可知i<j), s[j]-s[i]<=k. 对于MD条反感条件如(i,j,k). s[j]-s[i]>=k.

综上所述我们要建立一个具有n个顶点的有向图,其中需要满足:

2<=i<=n s[i-1]<=s[i] 且 好感条件(i,j,k) -> s[j]<= s[i]+k 且反感条件(i,j,k)-> s[i]<= s[j]-k 添加对应的边 i到i-1权值为0, i到j权值为k , j到i 权值为-k 的边即可.

然后我们用BellmanFord算法求1号点到其他所有点的最短距离即可.最后根据d[n]来输出结果.

现在有个问题,这个图不一定强连通.所以就算从1到点能到达的点不存在负圈,不代表其他的强连通分量里面没有负圈.也就是说就算从1号点能到N号点算出距离,可能该差分约束系统还是无解的.我们需要先用POJ1201

http://blog.csdn.net/u013480600/article/details/37922977中提到的1号方案判断一下该题是否有解,再用2号方案来求d[n].

AC代码: (代码并为考虑1号点不能到达其他强连通分量的情况)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 1e9
using namespace std;
const int maxn=1000+10;
const int maxm=50000+10;

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];
    bool inq[maxn];
    int cnt[maxn];
    int d[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++;
    }

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

        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 -1;
                    }
                }
            }
        }
        return d[n]==INF?-2:d[n];
    }
}BF;

int main()
{
    int n,ml,md;
    while(scanf("%d%d%d",&n,&ml,&md)==3)
    {
        BF.init(n);
        while(ml--)
        {
            int u,v,d;
            scanf("%d%d%d",&u,&v,&d);
            BF.AddEdge(u,v,d);
        }
        while(md--)
        {
            int u,v,d;
            scanf("%d%d%d",&u,&v,&d);
            BF.AddEdge(v,u,-d);
        }
        for(int i=2;i<=n;i++)
            BF.AddEdge(i,i-1,0);
        printf("%d\n",BF.bellmanford());
    }
    return 0;
}