J12 例题-5 公路网络

题目描述

喵国的公路网络由 $N$ 座城市和 $M$ 条公路组成，其中第 $i$ 条公路连接城市 $u_i,v_i$ ，其维护成本为 $c_i$ 。最优公路网络指的是选择这 $M$ 条公路中的若干条，使得 $N$ 座城市能互达且公路的维护成本之和最小。

现在喵国想进行公路网络的优化，他们计划进行 $Q$ 次考察，每次考察的内容为，若在城市 $t_i,g_i$ 之间新建一条维护成本为 $w_i$ 的公路，这条公路是否也在最优公路网中。

请你设计程序，对每次考察进行判断。

输入格式

共 $Q+M+1$ 行： 第一行三个整数 $N,M,Q$ ，依次表示城市数量，公路数量和考察次数； 接下来的 $M$ 行每行三个整数 $u_i,v_i,c_i$，依次表示第 $i$ 条公路连接的两个城市编号，以及对应的维护成本； 接下来的 $Q$ 行每行三个整数 $t_i,g_i,w_i$，依次表示第 $i$ 次考察对应的新建公路连接的两个城市编号，以及维护成本；

输出格式

$Q$ 行，每行一个字符串，若第 $i$ 次考察新建的公路在最小公路网中，输出 Yes ，否则输出 No。 注意，每个考察都是独立的。

样例输入1

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

样例输出1

Yes
No
Yes

样例1解析

公路网如上图所示，第 $1$ 次考察加入公路 $\{1,3,1\}$ ，最优公路网包含的 $\{1,2,2\},\{1,3,1\},\{2,4,5\},\{3,5,8\}$ ，输出 Yes 。

样例输入2

2 3 2
1 2 100
1 2 1000000000
1 1 1
1 2 2
1 1 5

样例输出2

Yes
No

数据范围

对于 $100 \%$ 的数据：$2\leq N,Q\leq 2\times 10^5,N-1\leq M\leq 2\times 10^5$ ，$1\leq u_i,v_i,t_i,g_i\leq N,$$1\leq c_i,w_i\leq 10^9$ ，保证查询中的公路与已有公路不同，保证图连通且没有重边和自环。