题解：P10928 走廊泼水节

1.题目分析

最小生成树，明显的 kruskal 。

2.题目思路

最小总权值和：

将原有的边按权值从小到大排序。

按次序依次遍历每条边，先更新答案，再将它们合并。

更新方法：

两个完全图合并成一个总共需要点数之积条边，减去一条原本树上的边。假设当前树边中最大的边权为 w ，则每条边的权值最小为 $w+1$ ，答案乘上 $w+1$ 即可。 （这是我第一次写洛谷题解，求大神指点）

3.题目代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int maxn=10000;
int f[maxn];
int s[maxn];
struct node{
	int x;
	int y;
	int w;
}a[maxn];
int t;
int n;
int ans;
void init(){
	for(int i=1;i<=n;i++) f[i]=i,s[i]=1;//父亲节点和并查集的大小要记得初始化 
}
bool cmp(node t1,node t2){
	return t1.w<t2.w;//按照边权从小到大排序 
}
int find(int x){
	if(f[x]==x) return x;
	return f[x]=find(f[x]);//路径压缩 
}
void kruskal(){
	ans=0;
	sort(a+1,a+n,cmp);
	for(int i=1;i<n;i++){
		int fx=find(a[i].x);
		int fy=find(a[i].y);
		ans+=(a[i].w+1)*(s[fx]*s[fy]-1);
		s[fx]+=s[fy],f[fy]=f[fx];
	}
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		init();
		for(int i=1;i<n;i++) scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].w);
		kruskal();
		printf("%d\n",ans);
	}
	return 0;
}