解题思路

又是一道差分约束题，题意就没看懂郁闷……看半天没看明白到底是哪几个相加又习惯性的去看了题解，发现是把那个集合中的几个元素加起来，其实这道题和之前做的那道差分约束题差不多，只是这道题没有保证连通性，所以需要加入一个超源点来保证图的连通性，其实就是选出一个点n+1为超源点，从这点向其他点连一条权值为0的边，其实直接可以把所有点都加入队列，并把dis数组都初始化为0。这题的不等关系给的还是很清楚的，就是要处理一下符号的问题题目给的是大于或者小于，要-1以后转换成小于等于建图，spfa判断是否存在环就行了。

图的构建：根据输入条件构建一个有向图，其中边的权重可以是负数。 SPFA算法：使用SPFA（Shortest Path Faster Algorithm）算法检测图中是否存在负权回路。 结果判断：如果SPFA算法检测到存在负权回路，则输出 "successful conspiracy"，否则输出 "lamentable kingdom"。

代码分析

图的构建： 输入包含多个边，每条边根据条件构建为正向或反向的边。 使用邻接表 g 存储图的结构。 SPFA算法： SPFA算法用于检测图中是否存在负权回路。 通过维护一个距离数组 dis 和一个入队次数数组 ind，检测是否存在节点入队次数超过节点总数，从而判断是否存在负权回路。 结果判断： 如果SPFA算法返回 false，说明存在负权回路，输出 "successful conspiracy"。 否则，输出 "lamentable kingdom"。

原理

SPFA算法：SPFA算法是Bellman-Ford算法的改进，用于检测单源最短路径中的负权回路。 负权回路检测：通过维护每个节点的入队次数，如果某个节点的入队次数超过节点总数，则说明存在负权回路。

实现步骤

输入处理： 读取输入的节点数 n 和边数 m。 根据输入条件构建图的邻接表。 SPFA算法实现： 初始化距离数组 dis 和入队次数数组 ind。 使用队列 q 存储待处理的节点。 遍历队列中的节点，更新相邻节点的距离，并检测是否存在负权回路。 结果输出： 如果SPFA算法检测到负权回路，输出 "successful conspiracy"。 否则，输出 "lamentable kingdom"。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 105
int n,m,dis[MAXN],ind[MAXN];
bool vis[MAXN];
struct Node
{
    int v,w;
};
vector<Node> g[MAXN];
bool spfa()
{
    memset(dis,0,sizeof(dis));
    memset(ind,0,sizeof(ind));
    queue<int> q;
    for(int i=0;i<=n;i++)
    {
        q.push(i);
        //vis[i]=true;
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=0;i<g[u].size();i++)
        {
            int v=g[u][i].v,w=g[u][i].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                    ind[v]++;
                    if(ind[v]>n)
                        return false;
                }
            }
        }
    }
    return true;
}
int main()
{
    while(scanf("%d",&n),n)
    {
        for(int i=0;i<=n;i++)
        {
            g[i].clear();
        }
        scanf("%d",&m);
        while(m--)
        {
            int si,ni,ki;
            char str[5];
            scanf("%d%d%s%d",&si,&ni,str,&ki);
            if(str[0]=='g')
            {
                Node temp;
                temp.v=si-1;
                temp.w=-ki-1;
                g[si+ni].push_back(temp);
            }
            else
            {
                Node temp;
                temp.v=si+ni;
                temp.w=ki-1;
                g[si-1].push_back(temp);
            }
        }
        if(spfa())
            printf("lamentable kingdom\n");
        else printf("successful conspiracy\n");
    }
}