AT_kupc2019_h.123パズル

你正在设计一个铅笔谜题。

这个谜题是由 $N$ 个顶点和 $M$ 条有向边组成的简单图。

顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。

边 $i$ 表示从顶点 $u_i$ 指向顶点 $v_i$，并且带有一个标签 $l_i\ (l_i \in \{0, 1\})$。

游戏规则如下：

• 在每个顶点上填入一个数字，可能是 $1, 2, 3$ 中的一个。顶点 $i$ 上写的数字记为 $A_i$。
• 对于所有边 $i\ (1 \leq i \leq M)$，符合以下条件的填法即为该谜题的解：
  • 如果 $l_i = 0$，则要求 $A_{u_i} < A_{v_i}$
  • 如果 $l_i = 1$，则要求 $A_{u_i} \leq A_{v_i}$

你发明了这个谜题，但是还没确认它是否有解。

即便没有解，你仍希望找到一个尽可能合理的解法。因此，你需要找到一种填法，使得不满意度降到最低。

不满意度的计算方式如下：

• 对于每条边 $i\ (1 \leq i \leq M)$，计算 $C_i$：
  • 如果 $l_i = 0$，则 $C_i = \max(0, A_{u_i} - A_{v_i} + 1)$
  • 如果 $l_i = 1$，则 $C_i = \max(0, A_{u_i} - A_{v_i})$
• 总不满意度为所有 $C_i$ 的和。

当谜题有解时，总不满意度可以达到 $0$。

请计算出不满意度的最小值。

输入以以下格式给出：

$N$ $M$ $u_1$ $v_1$ $l_1$ $u_2$ $v_2$ $l_2$ $:$ $u_M$ $v_M$ $l_M$

输出不满意度的最小值。

• $2 \leq N \leq 5000$
• $1 \leq M \leq \min(5000, N \times (N-1))$
• $1 \leq u_i, v_i \leq N$
• $u_i \neq v_i$
• 对于所有 $1 \leq i, j \leq N$，如果 $i \neq j$，那么 $(u_i, v_i) \neq (u_j, v_j)$
• $l_i \in \{0, 1\}$
• 输入的所有数值均为整数。

样例解释 1

选择 $A = (1, 2, 2, 3)$ 即可满足所有条件：

• $A_1 < A_2$
• $A_2 \leq A_3$
• $A_3 < A_4$
  此时不满意度为 $0$。

样例解释 2

选择 $A = (1, 2, 2, 2, 3, 2)$，此时 $C = (0, 0, 1, 0, 0, 0, 0, 0, 0)$，不满意度为 $1$。无法使不满意度为 $0$，因此不满意度的最小值为 $1$。

本翻译由 AI 自动生成