思路cpy自Anoxia_3,代码原创
做法:初始时先将每一个点看成一个大小为11的连通块,这个连通块就可以看成一个完全图(因为只有一个点)
做Kruskal算法,在每循环到一条可以合并两个连通块的边ee时,记ee的边长为ww,为了形成一个完全图,就要使得两个已经是完全图的连通块中的点有边,但是为了使最后的唯一最小生成树还是原来那棵而且,新增的边一定要大于ww:
假设新边小于w,因为新增边后会成环,当断开边e,形成的树大小会变小,即不是原来那棵,所以不成立
假设新边等于w,同样的断开e,会形成一个大小一样但结构不一样的树,不满足唯一,所以也不成立。
所以只要在每次新增e的时候,给两个连通块内的点增加w+1长的边即可。
#include <bits/stdc++.h>
#include <string.h>
#include <map>
#include <stack>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
const int M=2e4+10;
int n,m,k,T;
bool st[N];
int head[N],e[M],w[M],ne[M],tot;
struct node{
int x,y,z;
bool operator < (const node & b) const {
return z < b.z;
}
}edage[N];
int fa[N];
int cnt[N];
int getx(int x){
if(x!=fa[x]) fa[x]=getx(fa[x]);
return fa[x];
}
int merge(int a,int b,int z){
int sum=0;
int bx=getx(a);
int by=getx(b);
if(bx==by) return 0;
fa[bx]=by;
sum+=(cnt[by] * cnt[bx] -1) * (z+1);
cnt[by]+=cnt[bx];
return sum;
}
int main(){
int u,v,w;
cin>>T;
while(T--){
int res=0;
for(int i=0;i<N;i++){
fa[i]=i;
cnt[i]=1;
}
cin>>n;
for(int i=0;i<n-1;i++){
cin>>u>>v>>w;
edage[i]={u,v,w};
}
sort(edage,edage+n-1);
for(int i=0;i<n-1;i++){
res+=merge(edage[i].x,edage[i].y,edage[i].z);
}
cout<<res<<endl;
}
system("pause");
return 0;
}