UVA_515
这个题目是一个差分约束系统的题目。
我们设S[i]为第1至i个数的和，特别的，S[0]=0，根据题意可以列出如下三类不等式：
①当符号为gt时：S[s+n]-S[s-1]>=k
+ 1。
②当符号为lt时：S[s+n]-S[s-1]<=k-1。
③S[i]-S[i-1]>=-INF(0<i<=N)。
然后依据这些不等式进行建图后，用SPFA求最短路即可。
其中第③个式子主要是使图连通起来，同时，为了在使用SPFA时开始的时候只需将一个点入队，我们可以引入一个点作为第N+1个数字，且使S[N+1]=0（这个值是不是为0倒没有关系，只要合理即可），同时将第③个式子的-INF改写为-INF/1000，距离数组d[]初始化成INF。这样我们在开始时便只需将N+1入队，即可完成整个图的遍历。
如果“成功策反”那么就说明上面写的不等式不能完全满足，因而反映在图上就是某两点之间的最短路不存在，也就是说存在负圈。
#include<stdio.h>
#include<string.h>
#define MAXD 110
#define MAXM 1010
#define INF 1000000000
int d[MAXD], first[MAXD], next[MAXM], e, v[MAXM], w[MAXM];
int q[MAXD], inq[MAXD], inedq[MAXD], N, M;
char str[10];
void add(int a, int b, int c)
{
v[e] = b;
w[e] = c;
next[e] = first[a];
first[a] = e;
e ++;
}
int init()
{
int i, j, s, n, k;
scanf("%d", &N);
if(!N)
return 0;
scanf("%d", &M);
memset(first, -1, sizeof(first));
e = 0;
for(i = 0; i < M; i ++)
{
scanf("%d%d%s%d", &s, &n, str, &k);
if(str[0] == 'g')
add(s + n, s - 1, - k - 1);
else
add(s - 1, s + n, k - 1);
}
for(i = 0; i <= N; i ++)
add(i + 1, i, INF / 1000);
return 1;
}
int judge()
{
int i, u, front ,rear;
memset(inq, 0, sizeof(inq));
memset(inedq, 0, sizeof(inedq));
front = rear = 0;
for(i = 0; i <= N; i ++)
d[i] = INF;
d[N + 1] = 0;
q[rear ++] = N + 1;
while(front != rear)
{
u = q[front ++];
if(front > N)
front = 0;
inq[u] = 0;
for(i = first[u]; i != -1; i = next[i])
if(d[u] + w[i] < d[v[i]])
{
d[v[i]] = d[u] + w[i];
if(!inq[v[i]])
{
q[rear ++] = v[i];
if(rear > N)
rear = 0;
inq[v[i]] = 1;
if(inedq[v[i]] ++ > N)
return 1;
}
}
}
return 0;
}
int main()
{
while(init())
{
if(judge())
printf("successful conspiracy\n");
else
printf("lamentable kingdom\n");
}
return 0;
}