CH6201走廊泼水节-白红宇

CH6201走廊泼水节

阅读量：6945 次

发布时间：2019-06-27

本文共 1090 字，大约阅读时间需要 3 分钟。

题目链接：

【简化版题意】给定一棵N个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。求增加的边的权值总和最小是多少。
输入格式

本题为多组数据~
第一行t，表示有t组测试数据
对于每组数据
第一行N，表示水龙头的个数（当然也是OIER的个数）；
2到N行，每行三个整数X,Y,Z；表示水龙头X和水龙头Y有一条长度为Z的小道

输出格式

对于每组数据，输出一个整数，表示修建的所有道路总长度的最短值。

样例输入
231 2 21 3 341 2 32 3 43 4 5 
样例输出
417 
数据范围与约定

每个测试点最多10组测试数据
50% n<=1500;
100% n<=6000
100% z<=100

样例解释

第一组数据，在2和3之间修建一条长度为4的道路，是这棵树变成一个完全图，且原来的树依然是这个图的唯一最小生成树.

思路：先将所有边按边权排序，然后执行一个类似于Kruskall的过程，每次扫描到边(x,y,z)时，若x,y不在同一个集合，此时应该合并Sx,Sy,此时，对于x所在集合中除x之外的点u，y所在集合中除y之外的点v，完全图中u与v之间肯定要连一条边，有因为要保证边(x,y)一定在最小生成树中，就必须让(x,y)是连接两个集合的边权最小的边。所以(u,v)的边权最小为z+1.而Sx与Sy之间最后一共会增加(size[x]*size[y]-1)条边，所以把(z+1)*(size[x]*size[y]-1)累加到答案中即可

　　代码：

#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;const int N=6010;long long ans=0;int fa[N],size[N],T,n;struct E{int x,y,z;}e[N];bool operator<(const E &n1,const E &n2){return n1.z