POJ3169 Layout

题意简述

有 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;
}
查看评论