poj 1364 King （差分约束）

　　继续差分约束的题。如果是“lt”就构造(s+n+1)->(s)=-w+1的边，否则构造(s)->(s+n+1)=w+1的边。因为没有取等号，所以w要加减一。

　　因为没有其他限制，所以不用别的附加边。

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <queue>
 6 
 7 using namespace std;
 8 
 9 const int N = 111;
10 const int M = N * N;
11 const int INF = 0x55555555;
12 struct Edge {
13     int u, v, nx, c;
14 } edge[M];
15 int eh[N], ec;
16 
17 void init() {
18     memset(eh, -1, sizeof(eh));
19     ec = 0;
20 }
21 
22 void addedge(int u, int v, int w) {
23     edge[ec] = Edge{u, v, eh[u], w};
24     eh[u] = ec++;
25 }
26 
27 int dis[N];
28 bool bellman(int n) {
29     for (int i = 1; i <= n; i++) dis[i] = -INF;
30     dis[1] = 0;
31     bool ok;
32     for (int i = 0; i < n; i++) {
33         ok = true;
34         for (int j = 0; j < ec; j++) {
35             if (dis[edge[j].v] < dis[edge[j].u] + edge[j].c) {
36                 dis[edge[j].v] = dis[edge[j].u] + edge[j].c;
37                 ok = false;
38             }
39         }
40         if (ok) return true;
41     }
42     for (int j = 0; j < ec; j++) {
43         if (dis[edge[j].v] < dis[edge[j].u] + edge[j].c) return false;
44     }
45     return true;
46 }
47 
48 int main() {
49 //    freopen("in", "r", stdin);
50     int n, m;
51     while (~scanf("%d%d", &n, &m) && n) {
52         init();
53         int u, v, w;
54         char op[3];
55         for (int i = 0; i < m; i++) {
56             scanf("%d%d%s%d", &u, &v, op, &w);
57             v += u + 1;
58             if (op[0] == 'l') addedge(v, u, -w + 1);
59             else addedge(u, v, w + 1);
60         }
61         if (bellman(n)) puts("lamentable kingdom");
62         else puts("successful conspiracy");
63     }
64     return 0;
65 }

View Code

——written by Lyon