AT_abc243_e [ABC243E] Edge Deletion

题目描述

给定一个有 $N$ 个顶点、$M$ 条边的简单连通无向图。
第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$，长度为 $C_i$。

请删除若干条边，使得满足以下条件。请你求出最多可以删除多少条边。

• 删除边后，图仍然是连通的。
• 对于所有顶点对 $(s, t)$，删除前后顶点 $s$ 和顶点 $t$ 之间的距离不变。

输入格式

输入以如下格式从标准输入给出。

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 3
1 2 2
2 3 3
1 3 6

输出 #1

1

输入输出样例 #2

输入 #2

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

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

注释

简单连通无向图是指既简单又连通且边无方向的图。
图是简单的，意味着图中没有自环和重边。
图是连通的，意味着对于图中任意两个顶点 $s, t$，都可以通过若干条边从 $s$ 走到 $t$。
顶点 $s$ 和顶点 $t$ 之间的距离，指的是从 $s$ 到 $t$ 的最短路径长度。

数据范围

• $2 \leq N \leq 300$
• $N-1 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq A_i < B_i \leq N$
• $1 \leq C_i \leq 10^9$
• 若 $i \neq j$，则 $(A_i, B_i) \neq (A_j, B_j)$。
• 给定的图是连通的。
• 所有输入均为整数。

样例解释 1

删除边之前，所有顶点对之间的距离如下：

• 顶点 $1$ 和顶点 $2$ 之间的距离为 $2$
• 顶点 $1$ 和顶点 $3$ 之间的距离为 $5$
• 顶点 $2$ 和顶点 $3$ 之间的距离为 $3$
  即使删除第 $3$ 条边，所有顶点对之间的距离都不会改变。此外，无法再删除多于 $1$ 条边而满足题意，因此答案为 $1$。

样例解释 2

无法删除任何一条边。

由 ChatGPT 4.1 翻译