走廊泼水节（最小生成树求最小完全图）

传送门：走廊泼水节

思路：在求最小生成树的过程中会有很多连通块，合并每一个连通块时同时也要将两个连通块连成一个完全图，合并联通块的w是最长的一条边，也要保证是完全图求最小生成树时不变的一条边，所以额外连的边都必须>=w+1,连的边数是两个连通块的数量积减1，用一个res记录额外的边的总长

代码：

#include<iostream>
#include<cstring>
#include <cmath>
#include<algorithm>
#include <vector>
#include <stack>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
const int N=6010,M=N*N;
int n,m,k;
int f[N],cnt[N];
 
struct edge
{
    int a,b;
    double c;
}edges[N];
 
bool cmp(edge a,edge b)
{
    return a.c<b.c;
}
double get_dist(PII a,PII b)
{
    int dx=a.x-b.x;
    int dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}
int get(int x)
{
    if(f[x]==x)
       return x;
        return f[x]=get(f[x]);
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
         for(int i=1;i<n;i++)
         {
             int a,b,c;
             cin>>a>>b>>c;
             edges[i]={a,b,c};
         }
         sort(edges+1,edges+n,cmp);
         for(int i=1;i<=n;i++) f[i]=i,cnt[i]=1;
         int res=0;
         for(int i=1;i<n;i++)
         {
             int a=get(edges[i].a),b=get(edges[i].b),c=edges[i].c;
              if(a!=b)
              {
                  res+=(cnt[a]*cnt[b]-1)*(c+1);
                  cnt[b]+=cnt[a];
                  f[a]=b;
              }
         }
        cout<<res<<endl;
 
    }
        return 0;
}