学步园

题意：对于一个序列数字序列S。给出(si, ni, 0, ki)。

     
如果是(si,ni,gt,ki),意思就是存在约束条件S[si]+S[si+1]+...S[si+ni]
> ki，

     
如果是(si,ni,lt,ki),意思就是存在约束条件S[si]+S[si+1]+...S[si+ni]
<
ki  
     
判断所给的约束条件有无解，即是否存在这么一个序列S，有解就输出lamentable kingdom，无解就输出successful
conspiracy。

思路：将这些约束条件转化为差分约束，不妨设T[x] =
S[1]+S[2]+....S[x]，那么上面式子就可以转化为： 

   
 1. T[si+ni] - T[si-1] >
ki         
2. T[si+ni] - T[si-1] <
ki  

    
又差分约束系统的求解只能针对>=或<=，无法求解>的系统，还好ki是整数,可以很容易将<转化为<=  

    
1. T[si-1] - T[si+ni] <= -ki -
1   
2. T[si+ni] - T[si-1] <= ki -
1  

    
///////这想法是 一位叫依然的人的，直接copy过来了

差分约束问题 如果没给出源点，就得自己设一个超级源点，把所有的点连起来
这道题还有一个注意的是，点的个数，不是n个，而是N+2个！！！

#include <stdio.h>
#include <string.h>
#define VM 150
#define EM 300
#define inf 0x3f3f3f3f
int head[VM],ep;
struct edge
{
    int
v,w,next;
} e[EM];

void addedge (int cu,int cv,int cw)
{
    ep ++;
    e[ep].v =
cv;
    e[ep].w =
cw;
    e[ep].next =
head[cu];
    head[cu] =
ep;
}
int spfa (int n)
{
    int
vis[VM],dis[VM],cnt[VM],queue[VM];
    for (int i =
0; i <= n; i
++)   
//原来从1开始初始化wa了N遍
    {
       
vis[i] = 0;
       
cnt[i] = 0;
       
dis[i] = inf;
    }
    dis[n+2] =
0;
    int front =
0,rear = 0;
   
queue[rear++] = n+2;
    vis[n+2] =
1;
    cnt[n+2] =
1;
    while (front
!= rear)
    {
       
int u = queue[front];
       
front = (front+1)%(n+5);
       
vis[u] = 0;
       
for (int i = head[u]; i != -1; i = e[i].next)
       
{
           
int v = e[i].v;
           
if (dis[v] > dis[u] + e[i].w)
           
{
               
dis[v] = dis[u] + e[i].w;
               
if (!vis[v])
               
{
                   
vis[v] = 1;
                   
cnt[v] ++;
                   
if (cnt[v] >
n+1)   //原来有N+1个点，外加一个超级源点
所以是入队列次数>=n+2才有负环