Hdu 1531(差分约束)

Hdu 1531
题目很烦,慢慢体会。
1、SPFA的写法
2、SPFA判负环搞清楚有几个点
3、最短(长)路中的dis[i]表示 a[i]-a[0]的最大(小)值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define ms(i,j) memset(i, j, sizeof i);
const int MAXN = 100 + 5;
struct edge
{
int u, v, c;
}e[MAXN*MAXN];
int en;
struct sysdc
{
int dis[MAXN];
int vi[MAXN];
int cir[MAXN];
vector<int> G[MAXN];
int n;
void init(int n)
{
this->n = n;
for (int i=0;i<=n;i++)
{
G[i].clear();
}
}
int addedge(int a, int b, int c)//添加a-b>=c
{
en++;
e[en].u = b;
e[en].v = a;
e[en].c = c;
G[b].push_back(en);
}
int solve()
{
queue<int> q;
for (int i=0;i<=n;i++)
{
vi[i] = false;
cir[i] = 1;
dis[i] = 0;
q.push(i);
}
while (!q.empty())
{
int p = q.front(); q.pop();
vi[p] = false;
for (int i=0;i<G[p].size();i++)
{
edge ed = e[G[p][i]];
if (dis[p]+ed.c>dis[ed.v])
{
dis[ed.v] = dis[p]+ed.c;
if (!vi[ed.v])
{
vi[ed.v] = true;
cir[ed.v]++;
if (cir[ed.v]>n+1) return false;
q.push(ed.v);
}
}
}
}
return true;
}
}sdc;
int n, m;
void init()
{
en = 0;
sdc.init(n);
for (int i=1;i<=m;i++)
{
int si, ni, ki;
char oi, sb;
scanf("%d %d %c%c %d", &si, &ni, &oi, &sb, &ki);
if (oi=='g')//>
{
sdc.addedge(si-1, si+ni, ki+1);
} else sdc.addedge(si+ni, si-1, -ki+1);//<
}
}
void solve()
{
if (sdc.solve())
{
printf("lamentable kingdom\n");
} else printf("successful conspiracy\n");
}
int main()
{
while (scanf("%d%d", &n, &m)==2&&n&&m)
{
init();
solve();
}
return 0;
}

------ 本文结束 ------