测试地址
题目大意：给定一棵最小生成树，求以它为唯一的最小生成树的完全图（每两点之间都直接有边相连的图）的最小边权之和。
做法：首先把最小生成树中的边按边权从小到大排序，依次枚举每条边，根据Kruskal的求最小生成树思路可知，加入这条边前两点属于不同的集合，而这条边又一定是连接这两个集合的边中边权最小的（因为这是唯一的最小生成树），于是要构成满足条件的最小完全图，需要在两个集合之间连上（第一个顶点所在集合的点数*第二个顶点所在集合的点数-1）条边权为（当前边边权+1）的边，并把这些边权加入到答案中。然后只需要在并查集的合并操作中顺便维护集合内的点数即可。
以下是本人代码：
#include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; long n,a[20010]={0},b[20010]={0},c[20010]={0}; long f[20010]={0}; long long num[20010]={0},ans; long find(long x) { long r=x,i=x,j; while(f[r]!=r) r=f[r]; while(i!=r) {j=f[i];f[i]=r;i=j;} return r; } void merge(long a,long b) { long fa=find(a),fb=find(b); f[fa]=fb; num[fb]+=num[fa]; } void quicksort(long l,long r) { if (l>=r) return; long mid=c[(l+r)/2]; long i=l,j=r; while(i<=j) { while(c[i]<mid) i++; while(c[j]>mid) j--; if (i<=j) { long temp; temp=c[i];c[i]=c[j];c[j]=temp; temp=a[i];a[i]=a[j];a[j]=temp; temp=b[i];b[i]=b[j];b[j]=temp; i++;j--; } } quicksort(l,j); quicksort(i,r); } void input() { scanf("%ld",&n); for(int i=1;i<=n-1;i++) { scanf("%ld %ld %ld",&a[i],&b[i],&c[i]); ans+=c[i]; } for(int i=1;i<=n;i++) { f[i]=i; num[i]=1; } } void work() { for(int i=1;i<=n-1;i++) { long fa=find(a[i]),fb=find(b[i]); ans+=(num[fa]*num[fb]-1)*(c[i]+1); merge(a[i],b[i]); } } void output() { printf("%I64d",ans); } int main() { input(); quicksort(1,n-1); work(); output(); return 0; }
