← 返回题目列表

Codeforces · 1468/J

J. 道路改革

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

伯兰有 $$$n$$$ 个城市和 $$$m$$$ 双向道路。第 $$$i$$$ 条道路连接城市 $$$x_i$$$ 和 $$$y_i$$$,并具有速度限制 $$$s_i$$$。道路网络允许每个人从任何城市到达任何其他城市。

贝尔兰交通部正在计划进行道路改革。

首先,维护所有 $$$m$$$ 道路的成本太高,因此 $$$m - (n - 1)$$$ 道路将被拆除,而剩余的 $$$(n - 1)$$$ 道路仍然允许从任何其他城市到达任何城市。形式上,其余道路应代表一棵无向树。

其次,其余道路的速度限制可能会改变。更改将按顺序进行,每次更改要么将某些道路上的速度限制提高 $$$1$$$,要么将其降低 $$$1$$$。由于改变速度限制需要大量工作,该部希望尽量减少改变的次数。

该部的目标是建立一个由 $$$(n - 1)$$$ 条道路组成的道路网,所有道路的最高速度限制恰好等于 $$$k$$$。他们分配给您的任务是计算必须执行的最小速度限制更改次数,以便道路网络满足他们的要求。

例如,假设 Berland 的初始地图如下所示,并且 $$$k = 7$$$:

那么最佳的行动方案之一是拆除道路 $$$1$$$–$$$4$$$ 和 $$$3$$$–$$$4$$$,然后将道路 $$$2$$$–$$$3$$$ 的速度限制降低 $$$1$$$,因此最终的道路网络如下所示:

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$n - 1 \le m \le \min(2 \cdot 10^5, \frac{n(n-1)}{2})$$$; $$$1 \le k \le 10^9$$$) — 分别为城市数量、道路数量和所需的最高速度限制。

然后是 $$$m$$$ 行。第 $$$i$$$ 行包含三个整数 $$$x_i$$$、$$$y_i$$$ 和 $$$s_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$; $$$1 \le s_i \le 10^9$$$) — 由分别是第$$$i$$$条道路及其速度限制。所有道路都是双向的。

每个测试用例中的路网是连通的(即可以从任何其他城市沿道路行驶到达任何城市),并且每对城市最多由一条道路连接。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。同样,所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 部必须执行的最小更改次数,以便剩余 $$$(n - 1)$$$ 道路中的最大速度限制恰好为 $$$k$$$。

示例

输入 #1

4
4 5 7
4 1 3
1 2 5
2 3 8
2 4 1
3 4 4
4 6 5
1 2 1
1 3 1
1 4 2
2 4 1
4 3 1
3 2 1
3 2 10
1 2 8
1 3 10
5 5 15
1 2 17
3 1 15
2 3 10
1 4 14
2 5 8

输出 #1

1
3
0
0

注意

示例测试说明:

第一个测试用例在问题陈述中进行了描述。

在第二个测试用例中,道路网络最初看起来像这样:

该部可以拆除道路$$$1$$$–$$$2$$$、$$$3$$$–$$$2$$$和$$$3$$$–$$$4$$$,然后将道路$$$1$$$–$$$4$$$的速度限制提高三倍。

在第三个测试用例中,路网已经满足所有要求。

在第四个测试用例中,拆除道路 $$$1$$$–$$$2$$$ 就足够了,因此生成的道路网络满足要求。