POJ 1364 King(差分约束系统)

POJ 1364 King(差分约束系统)

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

题意:

有一个数字序列S={a1,a2,…an},它有m个子序列为 Si={a[si], a[si+1], a[si+2], … a[si+ni] }. 现在给出m个限制形式条件如下:

第i个子序列的和 <(or>) ki 的值.

问你是否存在这么一个S整数序列?

分析:

我们令S[i]= a1+a2+..+ai. 所以对于每一条约束条件比如:

a[si]+a[si+1]+…+a[si+ni]< ki . 我们可以转化为 S[si+ni] – S[si-1] <= ki-1.

这样就可以转化为了差分约束系统了.

该系统具有点的集合为0, 1,… n.其中对于S[si+ni] – S[si-1] <= ki-1条件我们可以得到 si-1 到 si+ni 的权值为ki-1的边.

对于a[si]+a[si+1]+…+a[si+ni] >ki 即 S[si+ni] – S[si-1] >=ki+1 我们可以得到 si+ni 到 si-1 的权值为-ki-1 的边.

然后由于是判断差分约束系统是否有解问题,我们还需要虚构一个超级源n+1号点.使得从n+1号点有边出来到0,1,…n号点且权值为0. 这样然后用BellmanFord算法即可判断是否有负权环了.

AC代码:

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=100+10;
const int maxm=10000+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];
    int d[maxn];
    bool inq[maxn];
    int cnt[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 bellmanford()
    {
        memset(inq,0,sizeof(inq));
        memset(cnt,0,sizeof(inq));
        queue<int> Q;
        for(int i=0;i<n;i++) d[i]= i==n-1?0:INF;
        Q.push(n-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 true;
                    }
                }
            }
        }
        return false;
    }
}BF;

int main()
{
    int n,m;
    while(scanf("%d",&n)==1&&n)
    {
        scanf("%d",&m);
        BF.init(n+2);
        while(m--)
        {
            int si,ni,ki;
            char str[10];
            scanf("%d%d%s%d",&si,&ni,str,&ki);
            if(str[0]=='l') BF.AddEdge(si-1,si+ni,ki-1);
            else if(str[0]=='g') BF.AddEdge(si+ni,si-1,-ki-1);
        }
        for(int i=0;i<=n;i++)   //超级源到其他所有点的边
            BF.AddEdge(n+1,i,0);
        printf("%s\n",BF.bellmanford()?"successful conspiracy":"lamentable kingdom");
    }
    return 0;
}