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 自动生成**