题目翻译:有n个数,m个限制条件。每一个限制条件形如:1.x y gt c:表示ax + ax+1 + … +ay > c。2.x y It c:表示ax + ax+1 + …… +ay < c。有解输出“lamentable kingdom”,否则输出“successful conspiracy”。
对于每一个限制条件,用前缀和的思想,就变成了Sy – Sx-1 > c 和 Sy – Sx-1 < c。于是就是一个典型的差分约束模型。不过差分约束必须满足 ’<=’,于是<x就转换成<= x – 1,> x就转换成>= x + 1。
建好图后跑spfa判负环即可。
但还有一个问题,就是应该从哪个节点开始?思考一下,我们只用判断图中是否存在负环,因此从那一个点开始都行,那么不放建一个超级源点,向所有点连一条边权为0的边。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int maxn = ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = ans * + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int n, m;
char s[];
struct Edge
{
int to, w, nxt;
}e[maxn << ];
int head[maxn], ecnt = ;
void addEdge(int x, int y, int w)
{
e[++ecnt] = (Edge){y, w, head[x]};
head[x] = ecnt;
} bool in[maxn];
int dis[maxn], cnt[maxn];
bool spfa(int s)
{
Mem(in, ); Mem(cnt, );
Mem(dis, 0x3f); dis[s] = ;
queue<int> q; q.push(s);
while(!q.empty())
{
int now = q.front(); q.pop();
in[now] = ;
for(int i = head[now]; i; i = e[i].nxt)
{
if(dis[e[i].to] > dis[now] + e[i].w)
{
dis[e[i].to] = dis[now] + e[i].w;
if(!in[e[i].to])
{
in[e[i].to] = ;
if(++cnt[e[i].to] > n + ) return ;
q.push(e[i].to);
}
}
}
}
return ;
} void init()
{
Mem(head, );
ecnt = ;
} int main()
{
while(scanf("%d", &n) && n)
{
m = read();
init();
for(int i = ; i <= m; ++i)
{
int x = read() + , y = read();
scanf("%s", s); int t = read();
if(s[] == 'g') addEdge(x + y, x - , - t - );
else addEdge(x - , x + y, t - );
}
for(int i = ; i <= n + ; ++i) addEdge(, i, );
printf("%s\n", spfa() ? "lamentable kingdom" : "successful conspiracy");
}
return ;
}