题目链接：【http://poj.org/problem?id=1364】
晕死了。但是也长知识了
题意：一个长度为n的序列：a[1]、a[2]、a[3]...a[n],然后给你一些约束条件：si、ni、gt||lt、ki表示：a[si]、a[si+1]、、、、a[si+ni]<or>ki,问你满足这些约束条件，字符串是否存在。存在输出：lamentable kingdom，否则输出：successful conspiracy
题解：对序列求前缀和，将约束条件改为：sum[si+ni]-sum[si-1]<or>ki，为了方便：我们使其小标从1开始：sum[si+ni+1]-sum[si]<or>ki;
但是：虽然我们可以根据上面的约束关系建立图，但是并不能保证图的联通，也就是说我们不一定能找到负环，我们可以对所有的点在加入一个相同的约束关系（这样做并不会影响最终的约束关系，但但是增加了图的连通性），添加约束关系的时候我们有两种方案：
1、建立超级点，这个超级点1和任意一个点的约束关系都一样。
2、在用SPFA求负环的时候，把所有的点加入队列并把dis[]初始化为零，（相当于建立了一个超级起点），然后判断是否有点入队的的次数大于N即可；
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 150; int N, M; int u, v, d; char s[15]; struct Edge { int id, next, len; Edge(int id = 0, int next = 0, int len = 0): id(id), next(next), len(len) {} } E[maxn]; int head[maxn], tot; void init() { memset(head, -1, sizeof(head)); tot = 0; } void adde(int u, int v, int len) { E[tot] = Edge{v, head[u], len}; head[u] = tot++; } int top, stk[maxn], num[maxn]; int dis[maxn], vis[maxn]; bool SPFA(int st, int N) { for(int i = 0; i <= N; i++) dis[i] = 0, vis[i] = 1, num[i] = 0;; for(int i = 0; i < N; i++) stk[i] = i + 1; top = N + 1; while(top) { int u = stk[--top]; vis[u] = 0; for(int k = head[u]; ~k; k = E[k].next) { int v = E[k].id; if(dis[v] > dis[u] + E[k].len) { dis[v] = dis[u] + E[k].len; if(vis[v]) continue; vis[v] = 1; stk[top++] = v; num[v]++; if(num[v] > N) return false; } } } return true; } int main () { while(scanf("%d", &N), N) { init(); scanf("%d", &M); for(int i = 1; i <= M; i++) { scanf("%d %d %s %d", &u, &v, s, &d); if(s[0] == 'l') adde(u, u + v + 1, d - 1);//保证下标从1开始 else adde(u + v + 1, u, -d - 1);//变成 " <= "; } bool ans = SPFA(1, N + 1); if(!ans) printf("successful conspiracy "); else printf("lamentable kingdom "); } return 0; }