描述
最小生成树P.S.S在宿命的指引下找到了巫师Kismi。P.S.S希望Kismi能帮自己变成一个完全图。Kismi由于某些不可告人的原因，把这件事交给了你。 PS: 可以保证，这个最小生成树对于最后求出的完全图是唯一的。 格式
输入格式
输入的第一行是一个整数n，表示生成树的节点数。 接下来有n-1行，每行有三个正整数，依次表示每条边的端点编号和边权。 （顶点的边号在1-n之间，边权
输出格式
一个整数ans，表示以该树为最小生成树的最小完全图的边权之和。
分析
根据Kruskal算法，将已有的最小生成树的边权从小到大排序，依次考察。当前边在添加之前，一定是连接两点所在集合的边权最小的边。所以两个集合之间的其他边的边权至少都是该边边权+1.
问题就转化成了，怎样快速判断该边两点所在并查集的大小？在并查集合并时以根节点为下标记录并查集大小即可。
int fa[maxn],f[maxn];
int find(
int a){
fa[a]==a ? a : fa[a]=find(fa[a]);
}
void merge(
int a,
int b){
int x=find(a),y=find(b);
f[b]+=f[a];
fa[x]=y;
}
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 21000
using namespace std;
long long fa[maxn],f[maxn],n;
int find(
int a){
return fa[a]==a ? a : fa[a]=find(fa[a]);
}
void merge(
int a,
int b){
long long x=find(a),y=find(b);
f[y]+=f[x];
fa[x]=y;
}
struct edge{
long long left,right,val;
}g[maxn];
bool operator < (
const edge &e1,
const edge &e2){
return e1.val<e2.val;
}
long long ans=
0;
int main(){
scanf(
"%d",&n);
for(
int i=
1;i<=n-
1;i++){
int a,b,c;
scanf(
"%lld%lld%lld",&g[i].left,&g[i].right,&g[i].val);
ans+=g[i].val;
}
sort(g+
1,g+n);
for(
int i=
1;i<=n;i++) {
fa[i]=i; f[i]=
1;
}
for(
int i=
1;i<=n-
1;i++){
int a=find(g[i].left);
int b=find(g[i].right),c=g[i].val;
ans+=(f[a]*f[b]-
1)*(c+
1);
merge(g[i].left,g[i].right);
}
printf(
"%lld",ans);
return 0;
}
}
转载于:https://www.cnblogs.com/leotan0321/p/6081406.html
