「SCOI2011」糖果 - 差分约束

发表于 更新于 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

幼儿园里有 \(N\) 个小朋友，lxhgww 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww 需要满足小朋友们的 \(K\) 个要求。幼儿园的糖果总是有限的，lxhgww 想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

要求分为 \(5\) 种，每种要求为 \((X, A, B)\)，含义如下：

  • 如果  \(X\) = \(1\)， 表示第  \(A\)  个小朋友分到的糖果必须和第  \(B\)  个小朋友分到的糖果一样多；

  • 如果  \(X\) = \(2\)， 表示第  \(A\)  个小朋友分到的糖果必须少于第  \(B\)  个小朋友分到的糖果；

  • 如果  \(X\) = \(3\)， 表示第  \(A\)  个小朋友分到的糖果必须不少于第  \(B\)  个小朋友分到的糖果；

  • 如果  \(X\) = \(4\)， 表示第  \(A\)  个小朋友分到的糖果必须多于第  \(B\)  个小朋友分到的糖果；

  • 如果  \(X\) = \(5\)， 表示第  \(A\)  个小朋友分到的糖果必须不多于第 \(B\) 个小朋友分到的糖果。

解题思路

很明显这是一道差分约束的题目。如何转化是本题的重点。

首先我们可以将 \(5\) 种情况分别转化。

\[ \begin{cases} A = B & X = 1 \\ A < B & X = 2 \\ A \geq B & X = 3 \\ A > B & X = 4 \\ A \leq B & X = 5 \end{cases} \]

由于差分约束无法处理大于号和小于号，又同时数据只涉及整数，我们可以做如下处理：

\[ x < y (x, y \in \mathbb{Z}) \Leftrightarrow x + 1 \leq y \]

于是我们可以把 \(2\) 和 \(4\) 情况加以转化，最终得出以下不等式：

\[ \begin{cases} A - B \geq 0 \vee B - A \geq 0 & X = 1 \\ B - A \geq 1 & X = 2 \\ A - B \geq 0 & X = 3 \\ A - B \geq 1 & X = 4 \\ A - B \geq 0 & X = 5 \end{cases} \]

由于不等式中都是大于等于号，我们可以用最长路解决。

不用最短路是因为最短路中出现了负权边，毫无关系的两个点的最短路大小关系会受到 \(0\) 的影响，若想得到正确答案则需要在除去超级源点的图的弱连通分量中分别寻找答案，码量巨大，及其难写。若使用最长路则不会出现负权边，不会出现该情况。

最终答案就是最终解的和。若解的最小值不等于 \(1\) ，由于差分性质，可以把所有解同时加一个数或减一个数，使最小值等于 \(1\) 后再求和。

同时要注意特判在 \(2\) 和 \(4\) 情况下 \(A\) 和 \(B\) 不能相等，否则无解。

最后注意一下由于这道题的图是稀疏图，且数据较大，所以求最长路只能用 已经死了的 SPFA，用 Bellman-Ford 会 TLE。

代码演示

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <utility>
#include <vector>
#include <queue>

const int MAXN = 100000, INF = 0x3f3f3f3f;

int n, k, cnt[MAXN + 1];
std::vector< std::pair<int, int> > e[MAXN + 1];
long long dis[MAXN + 1];
bool vis[MAXN + 1];
std::queue<int> q;

bool SPFA() {
    memset(dis, -0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));
    dis[0] = 0, vis[0] = true;
    q.push(0);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;

        for (auto ed : e[u]) {
            if (dis[ed.first] < dis[u] + ed.second) {
                dis[ed.first] = dis[u] + ed.second;
                cnt[ed.first] = cnt[u] + 1;
                if (cnt[ed.first] >= n + 1) return false;
                if (!vis[ed.first]) {
                    q.push(ed.first);
                    vis[ed.first] = true;
                }
            }
        }
    }

    return true;
}

int main() {
    std::cin >> n >> k;

    for (int i = 0; i < k; i++) {
        int x, a, b;
        scanf("%d%d%d", &x, &a, &b);

        if (x == 1) {
            e[a].push_back( std::make_pair(b, 0) );
            e[b].push_back( std::make_pair(a, 0) );
        } else if (x == 2) {
            if (a == b) {
                std::cout << "-1" << std::endl;
                return 0;
            } else e[a].push_back( std::make_pair(b, 1) );
        }else if (x == 3) e[b].push_back( std::make_pair(a, 0) );
        else if (x == 4) {
            if (a == b) {
                std::cout << "-1" << std::endl;
                return 0;
            } else e[b].push_back( std::make_pair(a, 1) );
        }
        else e[a].push_back( std::make_pair(b, 0) );
    }

    for (int i = 1; i <= n; i++) e[0].push_back( std::make_pair(i, 0) );

    if (SPFA()) {
        int minn = INF;
        long long sum = 0;
        for (int i = 1; i <= n; i++) {
            if (minn > dis[i]) minn = dis[i];
            sum += dis[i];
        }
        sum += (long long)n * (1 - minn);
        std::cout << sum << std::endl;
    } else std::cout << "-1" << std::endl;

    return 0;
}