1511：【SCOI2011】糖果

题目描述

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

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

幼儿园的糖果总是有限的，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$ 个小朋友分到的糖果。

输出格式

输出一行，表示 lxhgww 老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 $-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

样例解释 #1

• $N=5$ 个小朋友，$K=7$ 个要求。
• 要求：
  1. $X=1, A=1, B=2$：$a_1 = a_2$
  2. $X=2, A=3, B=2$：$a_3 < a_2$
  3. $X=4, A=4, B=1$：$a_4 > a_1$
  4. $X=3, A=4, B=5$：$a_4 \ge a_5$
  5. $X=5, A=4, B=5$：$a_4 \le a_5$（结合上一条，得 $a_4 = a_5$）
  6. $X=2, A=3, B=5$：$a_3 < a_5$
  7. $X=4, A=5, B=1$：$a_5 > a_1$
• 由 1 得 $a_1 = a_2$。
• 由 2 得 $a_3 < a_2 = a_1$。
• 由 3 得 $a_4 > a_1$。
• 由 4 和 5 得 $a_4 = a_5$。
• 由 6 得 $a_3 < a_5 = a_4$。
• 由 7 得 $a_5 = a_4 > a_1$。
• 结合 $a_4 > a_1$ 和 $a_3 < a_1$。
• 每个小朋友至少 $1$ 颗糖，且要求尽量少。
  • 令 $a_3 = 1$（最小），则 $a_1 = a_2 \ge 2$，$a_4 = a_5 \ge 3$。
  • 取 $a_1 = a_2 = 2$，$a_3 = 1$，$a_4 = a_5 = 3$，总和 $2+2+1+3+3=11$。
• 可以验证满足所有要求，且无法得到更小的总和，输出 $11$。

数据范围

• 对于 $30\%$ 的数据，保证 $N < 100$。
• 对于 $100\%$ 的数据，保证 $N < 100000$，$K \le 100000$，$1 \le X \le 5$，$1 \le A, B \le N$。

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB

注意：本题是差分约束系统的经典应用。将每个小朋友的糖果数 $a_i$ 看作变量，建立不等式：

• $X=1$：$a_A = a_B$ 转化为 $a_A \ge a_B$ 且 $a_A \le a_B$
• $X=2$：$a_A < a_B$ 转化为 $a_A \le a_B - 1$
• $X=3$：$a_A \ge a_B$
• $X=4$：$a_A > a_B$ 转化为 $a_A \ge a_B + 1$
• $X=5$：$a_A \le a_B$

另外，每个小朋友至少 $1$ 颗糖：$a_i \ge 1$。

由于求最小值，通常使用最长路（因为约束是 $\ge$ 形式）。注意要判断正环（无解情况）。由于 $N$ 可达 $10^5$，需要使用高效算法如 SPFA（可能被卡，但本题数据较友好）。