SCOI2011糖果

负环 差分约束 T3 P3275 [SCOI2011]糖果 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

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

输入格式

输入的第一行是两个整数 $N$，$K$。接下来 $K$ 行，表示这些点需要满足的关系，每行 $3$ 个数字，$X$，$A$，$B$。

• 如果 $X=1$， 表示第 $A$ 个小朋友分到的糖果必须和第 $B$ 个小朋友分到的糖果一样多；
• 如果 $X=2$， 表示第 $A$ 个小朋友分到的糖果必须少于第 $B$ 个小朋友分到的糖果；
• 如果 $X=3$， 表示第 $A$ 个小朋友分到的糖果必须不少于第 $B$ 个小朋友分到的糖果；
• 如果 $X=4$， 表示第 $A$ 个小朋友分到的糖果必须多于第 $B$ 个小朋友分到的糖果；
• 如果 $X=5$， 表示第 $A$ 个小朋友分到的糖果必须不多于第 $B$ 个小朋友分到的糖果；

输出格式

输出一行，表示 $\text{lxhgww}$ 老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 $-1$。

样例 #1

样例输入 #1

5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1

样例输出 #1

11

提示

对于 $30\%$ 的数据，保证 $N\le 100$

对于 $100\%$ 的数据，保证 $N\le 100000$

对于所有的数据，保证 $K\le 100000,1\le X\le 5,1\le A,B\le N$

思路

差分约束 （1）求不等式组的可行解 源点需要满足条件：从源点出发, 一定可以走到所有边 步骤： 1. 先将每个不等式 $x_i\le x_j+c_k$, 转化为一条从 $x_j$ 走到 $x_i$, 长度为 $c_k$ 的边 2. 找一个超级源点（从$x_i\le c$ 中得出）, 使得该源点一定可以遍历到所有边 3. 从源点求一遍单源最短路 1. 如果有负环, 则无解 2. 如果没有负环, 则$dist[i]$就是原不等式组的一个可行解 （2）如何求最大值或者最小值, 这里的最值指的是每个变量的最值 结论：如果求得是最小值, 则应该求最长路； 如果求的是最大值, 应该求最短路。 求 $x_i$ 最大值：求所有从 $x_i$ 出发, 构成的不等式链： $x_i\le x_j+c_1\le x_k+c_2+c_1\le ...\le c_1+c_2+c_3+...$ 得到一个上界, 最终$x_i$ 的最大值就是所有上界的最小值 求 $x_i$ 最小值：求所有从 $x_i$ 出发, 构成的不等式链： $x_i\ge x_j+c_1\ge x_k+c_2+c_1\ge ...\ge c_1+c_2+c_3+...$ 得到一个下界, 最终$x_i$ 的最小值就是所有下界的最大值

那么该题需要把不等式统一为 $x_i\ge x_j+c_k$：

• x = 1时, $x_A=x_B$ 对应的转换式为 $x_B\ge x_A$ , $x_A\ge x_B$
• x = 2时, $x_A<x_B$ 对应的转换式为 $x_B\ge x_A+1$
• x = 3时, $x_B\le x_A$ 对应的转换式为$x_A\ge x_B$
• x = 4时, $x_A>x_B$ 对应的转换式为 $x_A\ge x_B+1$
• x = 5时, $x_A\le x_B$ 对应的转换式为$x_B\ge x_A$

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
typedef long long LL;
int h[N], e[M], w[M], ne[M], idx;
int q[N], cnt[N];
LL dist[N];
int n, m;
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()
{
    memset(dist, -0x3f, sizeof dist);
    int hh = 0, tt = 1;
    q[0] = 0;
    dist[0] = 0;
    st[0] = true;
    int count = 1;
    while (hh != tt)
    {
        int t = q[--tt];
 
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                count++;
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] > n + 1 || count > 5000 * n)
                    return false;
                if (!st[j])
                {
                    st[j] = true;
                    q[tt++] = j;
                }
            }
        }
    }
 
    return true;
}
 
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--)
    {
        int x, a, b;
        cin >> x >> a >> b;
        if (x == 1)
            add(a, b, 0), add(b, a, 0);
        else if (x == 2)
            add(a, b, 1);
        else if (x == 3)
            add(b, a, 0);
        else if (x == 4)
            add(b, a, 1);
        else if (x == 5)
            add(a, b, 0);
    }
    for (int i = 1; i <= n; i++)
        add(0, i, 1);
 
    if (!spfa())
        cout << -1 << endl;
    else
    {
        LL res = 0;
        for (int i = 1; i <= n; i++)
            res += dist[i];
        cout << res << endl;
    }
 
    return 0;
}