幼儿园里有 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≤N<105,
1≤K≤105,
1≤X≤5,
1≤A,B≤N
输入样例：
5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1
输出样例：
11
思路：
/*
差分约束两大应用
应用一:
1 求不等式组的可行解
?源点需要满足的条件: 从源点出发,一定可以走到所有的边
否则 用单源最短路做的话 有一条边走不到 则该边对应的不等式就无法满足
某一个点x[i]走不到无所谓(某个点走不到代表它不受限制,x[i]取任意数都可以)
过程:
1 把每个x[i] ≤ x[j] + C[k]不等式转化为一条从x[j]走到x[i]长度为C[k]的边
2 然后在这个图上找一个超级源点,使得该源点一定可以遍历到所有边
3 从源点求一遍 单源最短路
3.1 假如存在负环
x[1]→x[2]→x[3]→x[k]
↑ c1 c2 c3 ↓
← ← ← ← ← ←
ck
x[2]≤ x[1]+c[1]
...
x[k]≤ x[k-1]+c[k-1]
x[1]≤ x[k]+c[k]
对第一个不等式用后面的不等式一直做松弛
x[2] ≤ x[1]+c[1]
≤ x[k]+c[k]+c[1]
≤ x[k-1]+c[k-1]+c[k]+c[1]
...
≤ x[2]+c[2]+...+c[k-1]+c[k]+c[1]
≤ x[2]+(小于零的Σc[i])
x[2] < x[2]
即矛盾
得出结论:不等式无解 <=> 存在负环
4 求完单源最短路之后
4.1 存在负环 => 不等式无解
4.2 没有负环 => 求完之后一定是满足这个不等式的 <=> 即一个可行解
x[i] ≤ x[j] + C[k]
x1 ≤ x2+1
{ x2 ≤ x3+2
x3 ≤ x1-5
x1 = 0
x2 = -1
x3 = -2
类比最短路
i→j 求之前 d[j] > d[i]+c
c 求完后 d[j] ≤ d[i]+c
一个图里每个点求完最短距离后每个点的最短距离都有第二个不等式满足
即 任何一个最短路问题 可以 转化为一个差分约束问题
同理 一个差分约束问题 可以 转化为一个单源最短路问题
最长路
i→j 求之前 d[j] < d[i]+c
c 求完后 d[j] ≥ d[i]+c
应用二:
2 如何求最大值或者最小值(x[i] for i in range(1,n))
结论1:如果求的是最小值,则应该求最长路,如果求的是最大值,则应该求最短路
问题1:如何转化x[i] ≤ c 其中c是一个常数 这类的不等式
方法:建立一个超级源点,0号点x[0],然后建立0→i 长度是c的边即可
x[i] ≤ c
<=>
x[i] ≤ x[0] + c = 0 + c
以求x[i]的最大值为例:所有从x[i]出发,构成的不等式链
x[i] ≤ x[j] + c[j]
≤ x[k] + c[k] + c[j]
≤ x[0] + c[1]+ c[2]+... + c[j]
= 0 + c[1]+ ... + c[j]
所计算出的上界,
最终x[i]的最大值
=所有上界的最小值
举例 x[i] ≤ 5
x[i] ≤ 2
x[i] ≤ 3
max(x[i]) = min(5,2,3) = 2
0 → 1 → 3 → 5 → ... → i
c1 c3 c5 ci-1
x[1] ≤ x[0] + c[1]
x[3] ≤ x[1] + c[3]
x[5] ≤ x[3] + c[5]
...
x[i] ≤ x[i-1] + c[i-1]
则
x[i] ≤ x[i-1] + c[i]
≤ x[i-3] + c[i-3] + c[i]
...
≤ x[0] + c[1] + c[3] + c[i-3] + c[i-1]
?可以发现Σc[i]就是从0→i的一条路径的长度
那么
求x[i]最大值
<=>
求所有上界的最小值
<=>
求所有从0→i的路径和的最小值
<=>
最短路求dist[i]
同理 求x[i]最小值
<=>
求所有下界的最大值
<=>
求所有从0→i的路径和的最大值
<=>
最长路求dist[i]
*/
/*
本题
1 A = B <=> A≥B B≥A
2 A < B <=> B≥A+1
3 A≥B <=> A≥B
4 A > B <=> A≥B+1
5 B≥A <=> B≥A
x≥1
} x≥x0+1(超级源点x0=0)
x0=1
举例 x[i] ≥ 5
x[i] ≥ 2
x[i] ≥ 3
min(x[i]) = 5
总共最小值 = min(x[i]最小值) for i in range(n)
= 求x[i]所有下界的最大值
= 求所有从0→i的路径和的最大值
= 最长路求dist[i]
0 → 1 → 3 → 5 → ... → i
c1 c3 c5 ci-1
x[1] ≥ x[0] + c[1]
x[3] ≥ x[1] + c[3]
x[5] ≥ x[3] + c[5]
...
x[i] ≥ x[i-1] + c[i-1]
则
x[i] ≥ x[i-1] + c[i]
≥ x[i-3] + c[i-3] + c[i]
...
≥ x[0] + c[1] + c[3] + c[i-3] + c[i-1]
?可以发现Σc[i]就是从0→i的一条路径的长度
那么 求x[i]最小值
<=>
求所有下界的最大值
<=>
求所有从0→i的路径和的最大值
<=>
最长路求dist[i]
即：
if(d[j]<d[i]+w[i][j])
d[j] = d[i] + w[i][j]
建立边数
最坏情况A = B <=> A≥B B≥A 2条
+超级源点和所有点xi建边
=3*n
*/
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 3e5 + 10;
int h[N], e[M], ne[M], w[M], idx;
int n, k;
int dist[N], st[N], cnt[N];
int stk[N], tt; // 数组模拟栈
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));
dist[0] = 0;
st[0] = 1;
stk[++tt] = 0;
while (tt != 0)
{
int t = stk[tt--];
st[t] = 0;
for (int i = h[t]; i != -1; 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 1;
if (!st[j])
{
st[j] = 1;
stk[++tt] = j;
}
}
}
}
return 0;
}
int main()
{
scanf("%d %d", &n, &k);
memset(h, -1, sizeof(h));
while (k--)
{
int a, b, x;
scanf("%d %d %d", &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
add(a, b, 0);
}
for (int i = 1; i <= n; i++)
add(0, i, 1);
if (spfa())
printf("-1\n");
else
{
LL res = 0;
for (int i = 1; i <= n; i++)
res += dist[i];
printf("%lld\n", res);
}
return 0;
}
