题目大意：给你n个数，组成一个集合s={a1,a2....an},再给你m个条件满足a[si]+a[si+1]...+a[si+ni] 后边一个关系，
比如第一个条件是 a[1]+a[2]+a[3]>0然后转化为s[3]-s[0]>0>=1
第二个条件是a[2]+a[3]+a[4]<2;转化为 s[4]-s[1]<2<=1
这是做的第一道差分约束题，问了好几个同志，最终差不多了，就过了
差分约束只是对于>= 或者<=使用，如果说求最大值的话，限制条件肯定是<=关系，然后建立图，求最短路径，找负环。相反的不说了。
引用discuss里几句
差分约束根本不需要什么附加顶点, 附加顶点的唯一
用处就是保证图的连通性, 不让你有负环判不到的情况,
解决这种问题的最佳途径就是初始把所有顶点都加入队列,
并且将所有dis置0, 这就相当于加了一个不存在的附加顶点,
它与所有的顶点的直连长度都是0，但是注意在判负环时必须是
"cnt>n"而不是"cnt>=n", 因为第一次所有顶点入队只是相当于
把一个附加顶点加入到队列中而已, 不应该算在cnt中, 如果在
此步骤没有增加过cnt, 则">="也是可以的.
解决：spfa，建图，本题根据建图不同求最短还是最长路也不一样，代码为求最短路,限制条件为<=
#include <iostream>
#include <queue>
using namespace std;
const int N=120;
const int MAX=0x3f3f3f3f;
struct node
{
int v,w,next;
};
node e[10000];
int head[N];
int dist[N];
bool inq[N];
int cnt[N];
int n,m;
int pos;
void init()
{
for(int i=0;i<=n;i++)
{//dist初始化为0，相当于添加一个超级源点n+1，到各个顶点的距离为0
head[i]=-1;
dist[i]=0;
inq[i]=0;
cnt[i]=0;
}
pos=0;
}
void addedge(int u,int v,int w)
{
e[pos].v=v;
e[pos].w=w;
e[pos].next=head[u];
head[u]=pos++;
}
bool spfa()
{
queue<int> q;//将各个顶点入队
for(int i=0;i<=n;i++)q.push(i);
int v,w,v0;
while(!q.empty())
{
v0=q.front();
q.pop();
inq[v0]=0;
for(int i=head[v0];i!=-1;i=e[i].next)
{
v=e[i].v;
w=e[i].w;
if(dist[v0]+w<dist[v])
{
dist[v]=dist[v0]+w;
if(!inq[v])
{
inq[v]=1;
q.push(v);//不能算第一个词入队，共有n+1个顶点所以判断条件为==n+1
if(++cnt[v] == n+1)return false;
}
}
}
}
return true;
}
int main()
{
char cmp[5];
int si,ni,k,i,j;
while(scanf("%d",&n),n)
{
init();
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d%d%s%d",&si,&ni,cmp,&k);
if(cmp[0]=='g')
addedge(si+ni,si-1,-k-1);
else
addedge(si-1,si+ni,k-1);
}
if(spfa())puts("lamentable kingdom");
else puts("successful conspiracy");
}
system("pause");
return 0;
}