poj 3169 Layout （差分约束）

　　继续差分约束。

　　这题要判起点终点是否连通，并且要判负环，所以要用到spfa。

　　对于ML的边，要求两者之间距离要小于给定值，于是构建(a)->(b)=c的边。同理，对于MD的，构建(b)->(a)=-c的边。然后就是(i+1)->(i)=0，两者距离大于0的限制。

代码如下：

 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 = 1111;
10 const int M = 33333;
11 struct Edge {
12     int t, nx, c;
13     Edge() {}
14     Edge(int t, int nx, int c) : t(t), nx(nx), c(c) {}
15 } edge[M];
16 int eh[N], ec;
17 
18 void init() {
19     memset(eh, -1, sizeof(eh));
20     ec = 0;
21 }
22 
23 void addedge(int s, int t, int c) {
24     edge[ec] = Edge(t, eh[s], c);
25     eh[s] = ec++;
26 }
27 
28 int cnt[N], dis[N], n;
29 bool inq[N];
30 queue<int> q;
31 const int INF = 0x5fffffff;
32 
33 int spfa(int s, int t) {
34     while (!q.empty()) q.pop();
35     for (int i = 1; i <= n; i++) inq[i] = false, dis[i] = INF, cnt[i] = n + 1;
36     q.push(s);
37     dis[s] = 0;
38     inq[s] = true;
39     cnt[s]--;
40     while (!q.empty()) {
41         int cur = q.front();
42         // cout << cur << ' ' << eh[cur] << endl;
43         q.pop();
44         inq[cur] = false;
45         for (int i = eh[cur]; ~i; i = edge[i].nx) {
46             Edge &e = edge[i];
47             //cout << dis[e.t] << ' ' << dis[cur] + e.c << endl;
48             if (dis[e.t] > dis[cur] + e.c) {
49                 dis[e.t] = dis[cur] + e.c;
50                 if (cnt[e.t]) cnt[e.t]--;
51                 else return -1;
52                 if (!inq[e.t]) {
53                     q.push(e.t);
54                     inq[e.t] = true;
55                 }
56             }
57         }
58     }
59     if (dis[t] == INF) return -2;
60     else return dis[t];
61 }
62 
63 int main() {
64     int ml, md;
65     int x, y, c;
66     while (~scanf("%d%d%d", &n, &ml, &md)) {
67         init();
68         for (int i = 0; i < ml; i++) {
69             scanf("%d%d%d", &x, &y, &c);
70             addedge(x, y, c);
71         }
72         for (int i = 0; i < md; i++) {
73             scanf("%d%d%d", &x, &y, &c);
74             addedge(y, x, -c);
75         }
76         for (int i = 1; i < n; i++) {
77             //cout << i + 1 << ' ' << i << endl;
78             addedge(i + 1, i, 0);
79         }
80         printf("%d
", spfa(1, n));
81     }
82     return 0;
83 }

View Code

——written by Lyon