← 返回题目列表

AtCoder · kupc2019_h

H. 123 个谜题

中文机器翻译题面 查看原题

配点 : 300 点

問題文

你正在制作铅笔谜题。

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

在顶点 1 减去 N 的数字位于两侧。 它们的编号最大为 1 减去 M 。

辺 i 是顶点 u_i 到顶点 v_i 是指向 的边,标签为 l_i (l_i \in \{0,1\}) 。

这个谜题的玩法如下。

  • 在每个顶点上写上数字 1,2,3 中的 1 个。写在顶点 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 。 请找出不满度的最小值

。

制約

  • 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\}
  • 所有输入均为整数。

入力

输入是按以下格式从标准输入给出的。

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

出力

输出不满度的最小值。


入力例 1

4 3
1 2 0
2 3 1
3 4 0

出力例 1

0

A = (1, 2, 2, 3) 。

此时,

  • A_1 < A_2
  • A_2 \leq A_3
  • A_3 < A_4

都满意,不满意程度为 0 。


入力例 2

6 9
1 2 1
2 3 1
3 4 0
4 5 0
1 6 0
6 2 1
6 3 1
4 6 1
6 5 0

出力例 2

1

A = (1, 2, 2, 2, 3, 2) ,那么 您可以使用C = (0, 0, 1, 0, 0, 0, 0, 0, 0) ,不满意程度为 它可以是 1 。 不满意程度 0 ,所以最低不满意程度是 1 。