← 返回题目列表

AtCoder · abc243_e

H. 边缘删除

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

分数: 500 点

问题陈述

给你一个简单的连通无向图 N 顶点和 M 边缘。
边缘 i 连接顶点 A_i 和顶点 B_i,长度为 C_i.

让我们在满足以下条件的同时删除一些边。求出可以删除的最大边数。

  • 删除后图形仍然是连接的。
  • 对于每对顶点 (s, t),之间的距离 s 和 t 删除前后保持不变。

注释

简单连通无向图是简单且连通且具有无向边的图。
当图没有自环和多边时,它是简单的。
对于每对两个顶点,图是连通的 s 和 t, t 可以从 s 通过遍历边。
顶点之间的距离 s 和顶点 t 是之间的最短路径的长度 s 和 t.

约束

  • 2 \leq N \leq 300
  • N-1 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq A_i \lt B_i \leq N
  • 1 \leq C_i \leq 10^9
  • (A_i, B_i) \neq (A_j, B_j) if i \neq j.
  • 给定的图形已连接。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

输出

打印答案。


示例输入 1

3 3
1 2 2
2 3 3
1 3 6

示例输出 1

1

删除前每对顶点之间的距离如下。

  • 顶点之间的距离 1 和顶点 2 is 2.
  • 顶点之间的距离 1 和顶点 3 is 5.
  • 顶点之间的距离 2 和顶点 3 is 3.

删除边 3 不影响任何一对顶点之间的距离。在满足条件的情况下不可能删除两条或多条边,所以答案是 1.


示例输入 2

5 4
1 3 3
2 3 9
3 5 3
4 5 3

示例输出 2

0

无法删除任何边。


示例输入 3

5 10
1 2 71
1 3 9
1 4 82
1 5 64
2 3 22
2 4 99
2 5 1
3 4 24
3 5 18
4 5 10

示例输出 3

5