POJ1364.md

差分约束，按题意建边，由于是判定是否有解，所以要设置一个超级源点，往每个点都连一条边权为0的边，然后判断正（负）环即可

#include<cstring>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int MAXN = 111;
const int INF = 0x3f3f3f3f;
int n,m,inq[MAXN],dist[MAXN];
bool vis[MAXN];
struct Graph{
    int tot,head[MAXN],nxt[MAXN<<3],to[MAXN<<3],cst[MAXN<<3];
    void init(){ tot = 0; memset(head,255,sizeof(head)); }
    void ADDEDGE(int u, int v, int c){
        tot++;
        nxt[tot] = head[u];
        to[tot] = v;
        cst[tot] = c;
        head[u] = tot;
    }
}G;
bool SPFA(){
    memset(inq,0,sizeof(inq));
    memset(vis,0,sizeof(vis));
    memset(dist,-INF,sizeof(dist));
    queue<int> que;
    dist[n+1] = 0;
    que.push(n+1);
    while(!que.empty()){
        int u = que.front();
        que.pop();
        vis[u] = false;
        for(int i = G.head[u]; ~i; i = G.nxt[i]){
            int v = G.to[i];
            int c = G.cst[i];
            if(dist[v]<dist[u]+c){
                dist[v] = dist[u] + c;
                if(!vis[v]){
                    vis[v] = true;
                    if(++inq[v]>n) return false;
                    que.push(v);
                }
            }
        }
    }
    return true;
}
int main(){
    while(scanf("%d",&n)!=EOF && n){
        scanf("%d",&m);
        G.init();
        for(int i = 1; i <= m; i++){
            int s,l,x;
            char op[4];
            scanf("%d %d %s %d",&s,&l,op,&x);
            if(op[0]=='g') G.ADDEDGE(s-1,s+l,x+1);
            else G.ADDEDGE(s+l,s-1,1-x);
        }
        for(int i = 1; i <= n; i++) G.ADDEDGE(n+1,i,0);
        if(!SPFA()) puts("successful conspiracy");
        else puts("lamentable kingdom");
    }
    return 0;
}