学步园

传送门：【HDU】1531 King

题目分析：差分约束！题目意思看了半天。。。。题目不难，但是陷阱很好。。。。

首先对于每个式子si ni gt ki，令v=si+ni，u=si-1，则有xv-xu>ki --> xv-xu>=ki+1 -->xu-xv<=-ki-1，可以建边(v,u,-ki-1)，对于每个式子si ni lt ki，令v=si+ni，u=si-1，则有xv-xu<ki --> xv-xu<=ki-1，可以建边(u,v,ki-1)，然后设立一个源点xs，对所有的xi建边(xs,xi,0)，跑一遍带负环判断的spfa，如果一个xi被更新了至少n+1次，那么说明题目中存在负环。否则没有负环。

坑爹的就是这至少n+1次。。我设成n次就错了。。。其实也对，加上s一共n+1个点。。。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )

const int MAXN = 105 ;
const int MAXQ = 105 ;
const int MAXE = 1000 ;
const int INF = 0x3f3f3f3f ;

struct Edge {
	int v , c ;
	Edge *next ;
	Edge () {}
	Edge ( int v , int c , Edge *next ) : v ( v ) , c ( c ) , next ( next ) {}
} E[MAXE] , *H[MAXN] , *cntE ;

int d[MAXN] ;
int in[MAXN] ;
bool inq[MAXN] ;
int Q[MAXN] , head , tail ;
int n , m ;
int s ;

void init () {
	cntE = E ;
	CLR ( H , 0 ) ;
}

void addedge ( int u , int v , int c ) {
	cntE -> v = v ;
	cntE -> c = c ;
	cntE -> next = H[u] ;
	H[u] = cntE ++ ;
}

bool spfa () {
	CLR ( in , 0 ) ;
	CLR ( inq , 0 ) ;
	CLR ( d , INF ) ;
	head = tail = 0 ;
	d[s] = 0 ;
	Q[tail ++] = s ;
	while ( head != tail ) {
		int u = Q[head ++] ;
		if ( head == MAXQ ) head = 0 ;
		inq[u] = 0 ;
		for ( Edge* e = H[u] ; e ; e = e -> next ) {
			int v = e -> v ;
			if ( d[v] > d[u] + e -> c ) {
				d[v] = d[u] + e -> c ;
				if ( !inq[v] ) {
					inq[v] = 1 ;
					if ( n + 1 == ++ in[v] )
						return false ;
					if ( d[v] < d[Q[head]] ) {
						if ( !head ) head = MAXQ ;
						Q[-- head] = v ;
					} else {
						Q[tail ++] = v ;
						if ( tail == MAXQ ) tail = 0 ;
					}
				}
			}
		}
	}
	return true ;
}

void solve () {
	int u , v , d ;
	char str[5] ;
	init () ;
	REP ( i , 0 , m ) {
		scanf ( "%d%d%s%d" , &u , &v , str , &d ) ;
		v += u ;
		-- u ;
		if ( !strcmp ( str , "gt" ) ) addedge ( v , u , - d - 1 ) ;
		else addedge ( u , v , d - 1 ) ;
	}
	s = n + 1 ;
	FOR ( i , 1 , n ) addedge ( s , i , 0 ) ;
	bool flag = spfa () ;
	printf ( "%s\n" , flag ? "lamentable kingdom" : "successful conspiracy" ) ;
}
	

int main () {
	while ( ~scanf ( "%d%d" , &n , &m ) && n )
		solve () ;
	return 0 ;
}