当前位置：首页 > news >正文

POJ 1364 King --差分约束第一题

news 来源：原创 2024/5/6 15:48:21

题意：求给定的一组不等式是否有解，不等式要么是：SUM(Xi) (a<=i<=b) > k (1) 要么是 SUM(Xi) (a<=i<=b) < k (2)

分析：典型差分约束题，变换，令Ti = SUM(Xj) (0<=j<=i). 则表达式(1)可以看做T(a+b)-T(a-1) > k,也就是T(a-1)-T(a+b) < -k，又因为全是整数,所以T(a-1)-T(a+b) <= -k-1. 同理，(2)看做T(a+b)-T(a-1) <= k-1.这样就化成了差分约束系统的题了。

在差分约束系统中，Xi - Xj <= K 的表达式建边为 <Xj,Xi> = K.

不存在这个序列的情况即为出现负环，所以这题建图后只需判断有无负环即可。这里用Bellman-Ford算法判负环

注意：

（1）a-1有可能为0,a+b有可能为n，所以如果按顶点来遍历边的话有n+1个顶点(0~n)。

（2）建的图可能不连通，可以通过附加点来使图联通，即令dis[] = {0}。相当于每个点都与一个附加点Vs相连，且边权为0.

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define Mod 1000000007
using namespace std;
#define N 107

struct Edge
{
    int v,next,w;
}G[N];
int head[N],tot;
int dis[N];
int n,m;

void addedge(int u,int v,int w)
{
    G[tot].v = v;
    G[tot].w = w;
    G[tot].next = head[u];
    head[u] = tot++;
}

bool Bellman_Ford()
{
    int i,j,k;
    memset(dis,0,sizeof(dis));
    for(i=0;i<=n;i++)   //n+1个节点
    {
        for(j=0;j<=n;j++)
        {
            for(k=head[j];k!=-1;k=G[k].next)
            {
                int v = G[k].v;
                int w = G[k].w;
                if(dis[v] > dis[j] + w)
                    dis[v] = dis[j] + w;
            }
        }
    }
    for(j=0;j<=n;j++)
    {
        for(k=head[j];k!=-1;k=G[k].next)
        {
            int v = G[k].v;
            int w = G[k].w;
            if(dis[v] > dis[j] + w)
                return false;
        }
    }
    return true;
}

int main()
{
    int u,v,w,i;
    char ss[5];
    while(scanf("%d",&n)!=EOF && n)
    {
        scanf("%d",&m);
        tot = 1;
        memset(head,-1,sizeof(head));
        for(i=0;i<m;i++)
        {
            scanf("%d%d%s%d",&u,&v,ss,&w);
            if(ss[0] == 'g')
                addedge(u+v,u-1,-w-1);
            else
                addedge(u-1,u+v,w-1);
        }
        if(!Bellman_Ford())
            puts("successful conspiracy");
        else
            puts("lamentable kingdom");
    }
    return 0;
}