【问题描述】

给出一张n个点,m条边的无向图,摧毁每条边都需要一定的体力,并且花费的体力值
各不相同,给定图中两个点x,y(x≠y),每当(x,y)之间存在路径,就需要不断摧毁当前
图中花费体力最少的一条边,直到该路径不联通。他定义cost(x,y)为摧毁(x,y)之间路径
花费的体力和。
他想要求出这个结果:

【输入格式】

第一行两个整数n,m,表示点数和边数。
接下来m 行,每行三个整数x,y,z,表示x和y之间存在一条花费体力为z的无向边。

【输出格式】

输出一个整数表示所求结果。其中i,j∈n 且i<j 。

【输入样例】

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

【输出样例】

256

【数据范围】

对 50%的输入数据:1≤n≤100;1≤m≤1000
对100%的输入数据:1≤n,m≤100000;1≤z≤100000

对于一条边连接的两个点(i,j)这条边能为答案做出贡献只有删除比它小的边,这两个连通块仍然连接的情况。

也就是说我们只需要考虑边权比它大或等于它的边存在时的联通状况,将边权从大到小排序,并查集看每加入一条边,点对的联通情况。

定义sum为当前存在边的边权总和。

如果这条边的两点不在一个连通块上,那么这条边以及比它小的边对答案的贡献就是sum*size[i]*size[j]然后再把i和j合并为一个连通块即可,之后sum减掉它。

否则sum直接减掉它(因为前面枚举大边的时候sum中已经包含它了)

下面是代码:

 

本文为原创文章,唯一地址链接:【Road】 转载请注明转自 stdKonjac

我来吐槽

*

*

取消

*