跳转至

排队布局

原题链接

题目描述

当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。

农夫约翰有 \(N\) 头奶牛，编号从 \(1\) 到 \(N\)，沿一条直线站着等候喂食。

奶牛排在队伍中的顺序和它们的编号是相同的。

因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上。

如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。

一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数 \(L\)。

另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数 \(D\)。

给出 \(M_L\) 条关于两头奶牛间有好感的描述，再给出 \(M_D\) 条关于两头奶牛间存有反感的描述。

你的工作是：如果不存在满足要求的方案，输出-1；如果 \(1\) 号奶牛和 \(N\) 号奶牛间的距离可以任意大，输出-2；否则，计算出在满足所有要求的情况下，\(1\) 号奶牛和 \(N\) 号奶牛间可能的最大距离。

差分约束

求最大值，我们用最短路来求解。

我们定义 \(dist[i]\) 为 \(i\) 号点距离 \(1\) 号点的距离。

可以得到以下约束条件：

  • \(dist[i]\ge dist[i-1]\Rightarrow dist[i-1]\le dist[i]\)
  • \(dist[a]-dist[b]\le L\Rightarrow dist[a]\le dist[b]+L~(a>b)\)
  • \(dist[a]-dist[b]\ge D\Rightarrow dist[b]\le dist[a]-D~(a>b)\)

因此可以推出：

  1. 如果问题无解，即存在负环。
  2. 如果有解， \(dist[n]=+\infty\) 答案即为 \(-2\)；否则为 \(dist[n]\)。

代码

 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
#include <bits/stdc++.h>
using namespace std;

const int N = 1010, M = 30000;
const int inf = 0x3f3f3f3f;

int n, m1, m2;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], cnt[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool spfa(int size) {
    memset(dist, 0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, false, sizeof st);

    queue<int> q;
    for (int i = 1; i <= size; i++) {
        q.push(i);
        st[i] = true;
        dist[i] = 0;
    }

    while (q.size()) {
        int u = q.front();
        q.pop();

        st[u] = false;

        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[u] + w[i]) {
                dist[j] = dist[u] + w[i];
                cnt[j] = cnt[u] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }

    return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    memset(h, -1, sizeof h);
    cin >> n >> m1 >> m2;
    while (m1--) {
        int a, b ,c;
        cin >> a >> b >> c;
        if (a < b) swap(a, b);
        add(b, a, c);
    }
    while (m2--) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a < b) swap(a, b);
        add(a, b, -c);
    }
    for (int i = 1; i <= n; i++) add(i, i - 1, 0);

    if (spfa(n)) cout << -1 << endl;
    else {
        spfa(1);
        int res = dist[n];
        if (res == inf) res = -2;
        cout << res << endl;
    }

    return 0;
}
回到页面顶部