POJ3169 Layout

十月 17, 2020 3559

题意简述

有 n 头奶牛编号 1 ~ n，要按照 1~n 的顺序站成一排，两头相邻的奶牛之间要有距离（也可以没有，我们可以认为他们坐标相同，同时可以认为奶牛是没有体积的）。
但是有几对奶牛互相讨厌，他们要求他们之间的距离最少不能少于某个数；有几对奶牛相互爱慕，他们要求他们之间的距离最多不能多于某个数。
现在把这些奶牛的要求告诉你，让你求编号 1 的奶牛与编号 n 的奶牛之间的最大距离是多少。如果无解，输出 -1；如果最大距离可以无限大，输出 -2。

解题思路

奶牛的限制条件可以抽象为不等式组。

令 d_i 表示第 i 头奶牛与第 1 头奶牛之间的距离，那么牛 i 和牛 j （i < j）间距不超过 k 等价于：

d_j - d_i \leq k

牛 i 和 牛 j 间距至少为 k 等价于：

d_j - d_i \geq k

同时我们知道奶牛还有一个从 1 到 n 的顺序，那么

d_i - d_{i - 1} \geq 0

把这三个条件连上边就 win 了。

当然还要注意一个点，就是图可能不连通，否则不可能会有无法到达的情况。
把 0 作为一个超级源点，从 0 向每一个点连一条边。跑最短路的时候先从 0 开始跑一遍判一下是不是有负环，再从 1 开始跑一遍输出答案。

代码实现

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
// Accepted

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;

using std::cin;
using std::cout;
using std::endl;

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 1000 + 10;

struct Edge {
    int v, w; Edge(int _v = 0, int _w = 0) : v(_v), w(_w) {}
};

int n, ml, md;
std::vector<Edge> G[MAXN];

int spfa(int s) {
    static int dis[MAXN]; memset(dis, 0x3f, sizeof dis);
    static bool inq[MAXN]; memset(inq, 0, sizeof inq);
    static int vis[MAXN]; memset(vis, 0, sizeof vis);
    dis[s] = 0;
    std::queue<int> q; q.push(s); inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        ++vis[u];
        if (vis[u] > n) return -1; // 负环
        // for (auto e : G[u]) {
        for (int i = 0, siz = (int) G[u].size(); i < siz; ++i) {
            Edge e = G[u][i];
            int v = e.v, w = e.w;
            if (dis[v] > dis[u] + w) {
                // 跑最短路
                dis[v] = dis[u] + w;
                if (!inq[v]) inq[v] = true, q.push(v);
            }
        }
    }
    return dis[n] == 0x3f3f3f3f ? -2 : dis[n];
}

int main() {
    n = read(); ml = read(); md = read();
    for (int i = 1; i <= ml; ++i) {
        int a = read(); int b = read(); int d = read();
        // (a < b)
        // (a) --- (b) <= d
        // dis[b] - dis[a] <= d
        // (b) <-- (a) : d
        // (a) --> (b) : d
        G[a].push_back(Edge(b, d));
    }
    for (int i = 1; i <= md; ++i) {
        int a = read(); int b = read(); int d = read();
        // (a < b) 
        // (a) --- (b) >= d
        // dis[b] - dis[a] >= d
        // dis[a] - dis[b] <= -d
        // (a) <-- (b) : -d
        // (b) --> (a) : -d
        G[b].push_back(Edge(a, -d));
    }
    for (int i = 2; i <= n; ++i) {
        // (i - 1 < i)
        // (i - 1) --- i >= 0
        // dis[i] - dis[i - 1] >= 0
        // dis[i - 1] - dis[i] <= 0
        // (i - 1) <-- i : 0
        // i --> (i - 1) : 0
        G[i].push_back(Edge(i - 1, 0));
    }
    for (int i = 1; i <= n; ++i) {
        // 防止不连通用的超级源点
        G[0].push_back(Edge(i, 0));
    }
    if (spfa(0) == -1) puts("-1");
    else printf("%d\n", spfa(1));
    return 0;
}