题目描述
幼儿园里有 \(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\)。
当我们的不等式有多个解
\[\left \{ \begin{array}c x_i\le a_0 \\x_i\le a_1 \\x_i\le a_2 \\....\\ x_i\le a_m \end{array} \right. \]的时候，我们的\(x_i\)肯定是满足\(x_i\le aMAX\)的，这个从不等式的解集在数轴上的表现就可以看出来，所以我们就是跑一条从\(0\)到\(i\)的最长路，就可以求出最小值了。
代码
#include <iostream>
#include <stack>
#include <cstring>
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 <int> 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;
}