题目描述

幼儿园里有 \(N\) 个小朋友，老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。

但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， 老师需要满足小朋友们的 \(K\) 个要求。

幼儿园的糖果总是有限的，老师想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

(相关资料图)

输入格式

输入的第一行是两个整数 \(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\) 个小朋友分到的糖果。

小朋友编号从 \(1\) 到 \(N\)。

输出格式

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

数据范围

\(1 \le N < 10^5\),\(1 \le K \le 10^5\),\(1 \le X \le 5\),\(1 \le A,B \le N\),输入数据完全随机。

解题思路

\(\qquad\)这道题目有很多不等式，想要求出不等式每个元对应的最小解，最后的和才会是最小的，我们应该采用最长路。所以这题的解题步骤如下：

\(\qquad\)\(1.\)首先将不等式进行转换，对于不等式\(x_i\le x_j+c_k\)，可以转化成\((j,i,c)\)这样的边。\(\qquad2.\)然后找到一个超级源点，使得它一定可以到达图中的所有边\(\qquad3.\)然后跑一遍超级源点的\(SPFA\)最长路，跑的结果有两种：

\(\qquad\quad a.\)图中存在正环，代表无解，输出\(-1\)

\(\qquad\quad b.\)图中不存在正环，统计最长路之和，输出。

为什么可以这样求？因为在一张图中，我们要求\(x_i\)的最大值，有这样的一个不等式组：

我们每一条从源点到\(x_i\)的路径都可以拉出这样一条不等式链：\(\quad \large x_i\le x_j+c_0\le x_k+c_1+c_0....\le x_0+c_0+c_1+c_2+c_3...+c_m\)

此时放到我们的差分约束系统建立条件中，等价于我们建立了一条\(0->i\)的边，权值是\(c_0+c_1+c_2+c_3...+c_m\)。

当我们的不等式有多个解

的时候，我们的\(x_i\)肯定是满足\(x_i\le aMAX\)的，这个从不等式的解集在数轴上的表现就可以看出来，所以我们就是跑一条从\(0\)到\(i\)的最长路，就可以求出最小值了。

代码

#include #include #include using namespace std;using LL = long long;const int N = 1e5 + 10, M = 3 * N + 10;int h[N], e[M], w[M], ne[M], idx;LL dist[N];int st[N], n, m, ring, cnt[N];void add(int a, int b, int c) {    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;}LL spfa() {    memset(dist, 0xcf, sizeof dist);    memset(st, 0, sizeof st);    memset(cnt, 0, sizeof cnt);        stack  q;    q.push(0), dist[0] = 0, st[0] = 1;        while (!q.empty())     {        auto t = q.top(); q.pop();        st[t] = 0;                for (int i = h[t]; ~i; i = ne[i])         {            int j = e[i];            if (dist[j] < dist[t] + w[i])             {                dist[j] = dist[t] + w[i];                cnt[j] = cnt[t] + 1;                if (cnt[j] >= n + 1) return ring = 1;                if (!st[j]) st[j] = 1, q.push(j);            }        }    }        LL res = 0;    for (int i = 1; i <= n; i ++ ) res += dist[i];    return res;}int main() {    scanf("%d%d", &n, &m);        memset(h, -1, sizeof h);    while (m -- )      {        int op, u, v;        scanf("%d%d%d", &op, &u, &v);        if (op == 1) add(v, u, 0), add(u, v, 0);        if (op == 2) add(u, v, 1);        if (op == 3) add(v, u, 0);        if (op == 4) add(v, u, 1);        if (op == 5) add(u, v, 0);    }    for (int i = 1; i <= n; i ++ ) add(0, i, 1);        ring = 0;    LL t = spfa();        if (ring) puts("-1");    else printf("%lld\n", t);        return 0;}