# POJ 1364 King （差分约束）

King

 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 13052 Accepted: 4684

Description

Once, in one kingdom, there was a queen and that queen was expecting a baby. The queen prayed: “If my child was a son and if only he was a sound king.” After nine months her child was born, and indeed, she gave birth to a nice son.

Input

The input consists of blocks of lines. Each block except the last corresponds to one set of problems and king’s decisions about them. In the first line of the block there are integers n, and m where 0 < n <= 100 is length of the sequence S and 0 < m <= 100 is the number of subsequences Si. Next m lines contain particular decisions coded in the form of quadruples si, ni, oi, ki, where oi represents operator > (coded as gt) or operator < (coded as lt) respectively. The symbols si, ni and ki have the meaning described above. The last block consists of just one line containing 0.

Output

The output contains the lines corresponding to the blocks in the input. A line contains text successful conspiracy when such a sequence does not exist. Otherwise it contains text lamentable kingdom. There is no line in the output corresponding to the last “null” block of the input.

Sample Input

4 2
1 2 gt 0
2 2 lt 2
1 2
1 0 gt 0
1 0 lt 0
0

Sample Output

lamentable kingdom
successful conspiracy

### 思路

1 2 gt 0 (a1+a2+a3>0)
2 2 lt 2 (a2+a3+a4<2)

a b gt c
S[a−1]−S[a+b]<=−c−1

a b lt c
S[a+b]−S[a−1]<=c−1

gt: <a+b,a−1>=−c−1

lt: <a−1,a+b>=c−1

### AC 代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
#include<queue>
#include<map>
#define INF (1<<25)
#define MAXN 30100

int n,m;

struct node
{
int s;
int t;
int w;
void init(int s,int t,int w)
{
this->s=s;
this->t=t;
this->w=w;
}
} edge;

int d;
bool bf()   //bellman_ford 先n^2一次再判断是否还可以继续优化，若可以则存在负环
{
memset(d,0,sizeof(d));
for(int i=1; i<=n; i++)
for(int j=0; j<m; j++)
if(d[edge[j].s]+edge[j].w<d[edge[j].t])
d[edge[j].t]=d[edge[j].s]+edge[j].w;
for(int i=0; i<m; i++)
if(d[edge[i].s]+edge[i].w<d[edge[i].t])
return false;
return true;
}

int main()
{
while(~scanf("%d",&n)&&n)
{
scanf("%d",&m);
int from,to,val;
char str;
for(int i=0; i<m; i++)
{
scanf("%d%d%s%d",&from,&to,str,&val);
if(str=='g')
edge[i].init(from+to,from-1,-val-1);
else
edge[i].init(from-1,from+to,val-1);
}
printf(!bf()?"successful conspiracy\n":"lamentable kingdom\n");
}
return 0;
}