比较简单的差分约束,注意由于差分约束只能处理<=(>=)的不等式,所以要处理一下value
另外判断负权回路要先将出现的元素入队一次,不然会WA
#include <iostream> #include <string.h> using namespace std; const int MAXN = 110; const int MAXM = MAXN*MAXN; struct node { int v, w, next; }mapp[MAXM]; int id; int head[MAXN]; void init() { memset(head, -1, sizeof(head)); id = 0; } void addedge(int u, int v, int value) { mapp[id].v = v, mapp[id].w = value, mapp[id].next = head[u], head[u] = id ++; } int dist[MAXN]; bool inque[MAXN]; const int inf = 1 << 30; int in[MAXN] = {0}; int que[100*MAXN]; int front, rear; bool SPFA(int s, int n) { for (int i = 0; i <= n; i ++){ dist[i] = inf; } que[rear ++] = s; inque[s] = true; dist[s] = 0; in[s] = 1; while (front < rear){ int pre = que[front ++]; inque[pre] = false; //if (in[pre] > n)return false; for (int i = head[pre]; i != -1; i = mapp[i].next){ if (dist[mapp[i].v] > dist[pre] + mapp[i].w){ dist[mapp[i].v] = dist[pre] + mapp[i].w; if (!inque[mapp[i].v]){ inque[mapp[i].v] = true; in[mapp[i].v] ++; que[rear ++] = mapp[i].v; if (in[mapp[i].v] > n+n)return false; } } } } return true; } int main() { int n, m; while (scanf("%d", &n) &&n){ init(); scanf("%d", &m); front = rear = 0; memset(inque, false, sizeof(inque)); memset(in, 0, sizeof(in)); for (int i = 0; i < m; i ++){ int a, b, c; char t[6]; scanf("%d%d%s%d", &a, &b, t, &c); if (t[0] == 'l'){ addedge(a-1, a+b, c-1); } else addedge(a+b, a-1, -(c+1)); if (!inque[a+b]){ que[rear ++] = a+b; inque[a+b] = true; in[a+b] ++; } if (!inque[a-1]){ que[rear ++] = a-1; inque[a-1] = true; in[a-1] ++; } } if (SPFA(0, n)) printf("lamentable kingdom\n"); else printf("successful conspiracy\n"); } return 0; }