# [POJ 1364] King【差分约束系统】

• 2018-01-05
• 0
• 0

## Problem:

 Time Limit: 1000MS Memory Limit: 10000K

Description

Once, in one kingdom, there was a queen and that queen was expecting a baby. The queen prayed: "If my child was a son and if only he was a sound king.'' After nine months her child was born, and indeed, she gave birth to a nice son.

Input

The input consists of blocks of lines. Each block except the last corresponds to one set of problems and king's decisions about them. In the first line of the block there are integers n, and m where 0 < n <= 100 is length of the sequence S and 0 < m <= 100 is the number of subsequences Si. Next m lines contain particular decisions coded in the form of quadruples si, ni, oi, ki, where oi represents operator > (coded as gt) or operator < (coded as lt) respectively. The symbols si, ni and ki have the meaning described above. The last block consists of just one line containing 0.

Output

The output contains the lines corresponding to the blocks in the input. A line contains text successful conspiracy when such a sequence does not exist. Otherwise it contains text lamentable kingdom. There is no line in the output corresponding to the last "null'' block of the input.

Sample Input

```4 2
1 2 gt 0
2 2 lt 2
1 2
1 0 gt 0
1 0 lt 0
0```

Sample Output

```lamentable kingdom
successful conspiracy```

Source

Central Europe 1997

## Solution:

• 若 o 为 gt (>)，则 S[s + n] - S[s - 1] > k，化为三角不等式即 S[s - 1] ≤ S[s + n] - k - 1
• 若 o 为 lt (<)，则 S[s + n] - S[s - 1] < k，化为三角不等式即 S[s + n] ≤ S[s - 1] + k - 1

【SPFA 判负权环】

## Code: O(M) ~ O(NM) [164K, 0MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int n, m;

struct Edge{
int np, val;
Edge *nxt;
};

struct Graph{
Edge *V, E;
int tope;

inline void clear() {tope = 0, memset(V, 0, sizeof(V));}

inline void addedge(int u, int v, int w){
E[++tope].np = v, E[tope].val = w;
E[tope].nxt = V[u], V[u] = &E[tope];
}
} G;

struct qnode{
int id, step;

qnode() {}
qnode(int id, int step): id(id), step(step) {}
};

struct queue{
#define inc(x) (x) = ((x) == 104 ? 1 : (x) + 1)
qnode node;
int fr, re;

inline void clear() {fr = re = 0;}

inline bool empty() {return fr == re;}

inline void push(const qnode &x) {node[re] = x, inc(re);}

inline void pop() {inc(fr);}

inline qnode front() {return node[fr];}
} q;

int dis;
bool inq;

inline bool SPFA_negative_cycle(){
memset(dis, 0, sizeof(dis)), q.clear();
for(register int i = 0; i <= n; i++)
q.push(qnode(i, 1)), inq[i] = 1;
while(!q.empty()){
qnode u = q.front();
q.pop(), inq[u.id] = 0;
for(register Edge *ne = G.V[u.id]; ne; ne = ne->nxt)
if(dis[u.id] + ne->val < dis[ne->np]){
dis[ne->np] = dis[u.id] + ne->val;
if(u.step == n + 1) return 1;
// If the number of the points on a path exceeds n + 1, there must be negative cycles
// Beware that the number of points is n + 1 (identified as 0 ~ n), but not n !!!
q.push(qnode(ne->np, u.step + 1)), inq[ne->np] = 1;
}
}
return 0;
}

int main(){
while(scanf("%d", &n) != EOF && n){
scanf("%d", &m);
G.clear();
for(register int i = 1; i <= m; i++){
int s, n, k;
char o;
scanf("%d%d%s%d", &s, &n, o, &k);
if(o == 'g') G.addedge(s + n, s - 1, -k - 1);
else G.addedge(s - 1, s + n, k - 1);
}
if(SPFA_negative_cycle()) puts("successful conspiracy");
else puts("lamentable kingdom");
}
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai