← 返回题目列表

Codeforces · 1108/F

F. MST 统一

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

给你一个无向加权连通图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边,没有循环和多条边。

第 $$$i$$$ 条边是 $$$e_i = (u_i, v_i, w_i)$$$;沿边 $$$e_i$$$ 的顶点 $$$u_i$$$ 和 $$$v_i$$$ 之间的距离为 $$$w_i$$$ ($$$1 \le w_i$$$)。该图是连通的,i。 e.对于任何一对顶点,它们之间至少存在一条仅由给定图的边组成的路径。

正权重情况下的最小生成树 (MST) 是连接的加权无向图的边的子集,该图将所有顶点连接在一起,并且在所有此类子集中具有最小的总成本(总成本是所选边的成本之和)。

您可以修改给定的图表。您可以执行的唯一操作如下:将某些边的权重增加$$$1$$$。您可以将每条边的权重增加数倍(可能是零)。

假设初始 MST 成本为 $$$k$$$。你的问题是用尽可能少的操作数增加一些边的权重,使得获得的图中 MST 的成本保持为 $$$k$$$,但 MST 是唯一的(这意味着在获得的图中只有一种方法可以选择 MST)。

您的问题是计算执行此操作所需的最少操作数。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5, n - 1 \le m \le 2 \cdot 10^5$$$) — 初始图中的顶点数和边数。

接下来的 $$$m$$$ 行每行包含三个整数。第 $$$i$$$ 行包含第 $$$i$$$ 边 $$$e_i$$$ 的描述。它由三个整数 $$$u_i、v_i$$$ 和 $$$w_i$$$ 表示($$$1 \le u_i, v_i \le n, u_i \ne v_i, 1 \le w \le 10^9$$$),其中 $$$u_i$$$ 和 $$$v_i$$$ 是由第 $$$i$$$ 条边连接的顶点, $$$w_i$$$ 是这条边的权重。

保证给定的图不包含循环和多条边(即,对于从 $$$1$$$ 到 $$$m$$$ $$$u_i \ne v_i$$$ 的每个 $$$i$$$ ,并且对于每个无序的顶点对 $$$(u, v)$$$ ,最多有一条边连接这对顶点)。还保证给定的图是连通的。

输出

打印一个整数 — 在不改变 MST 成本的情况下统一初始图的 MST 的最少操作数。

示例

输入 #1

8 10
1 2 1
2 3 2
2 4 5
1 4 2
6 3 3
6 1 3
3 5 2
3 7 1
4 8 1
6 2 4

输出 #1

1

输入 #2

4 3
2 1 3
4 3 4
2 4 1

输出 #2

0

输入 #3

3 3
1 2 1
2 3 2
1 3 3

输出 #3

0

输入#4

3 3
1 2 1
2 3 3
1 3 3

输出#4

1

输入 #5

1 0

输出 #5

0

输入 #6

5 6
1 2 2
2 3 1
4 5 3
2 4 2
1 4 2
1 5 3

输出 #6

2

注意

第一个例子对应的图片:

例如,您可以将边 $$$(1, 6)$$$ 或 $$$(6, 3)$$$ 的权重增加 $$$1$$$ 以统一 MST。

最后一个例子对应的图片:

例如,您可以将边 $$$(1, 5)$$$ 和 $$$(2, 4)$$$ 的权重增加 $$$1$$$ 以统一 MST。