对于完全图 G，若有且仅有一棵最小生成树为 T，则称完全图 G 是树 T 扩展出的。
给你一棵树 T，找出 T 能扩展出的边权和最小的完全图 G。
第一行 N 表示树 T 的点数；
接下来 N−1 行三个整数 Si,Ti,Di；描述一条边（Si,Ti）权值为 Di；
保证输入数据构成一棵树。
输出仅一个数，表示最小的完全图 G 的边权和。
样例输入
4
1 2 1
1 3 1
1 4 2
样例输出
12
这道题解法很巧妙，还是从小到大排序，一条一条往上加。往上加的同时，记录sum[i]表示以i为根节点的树中含点的个数，很显然，一次操作中所加的边权就是（sum[i]+sum[j]-1）*(v+1)+v其中i表示加入边的起点，j表示终点，v表示边权代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define MAXN 100010
#define INF 2147483647
#define MOD 10000007
#define LL long long
#define in(a) a=read()
#define REP(i,k,n) for(int i=k;i<=n;i++)
#define DREP(i,k,n) for(int i=k;i>=n;i--)
#define cl(a) memset(a,0,sizeof(a))
inline int read(){
int x=
0,f=
1;
char ch=
getchar();
for(;!isdigit(ch);ch=getchar())
if(ch==
'-') f=-
1;
for(;isdigit(ch);ch=getchar()) x=x*
10+ch-
'0';
return x*
f;
}
inline void out(
int x){
if(x<
0) putchar(
'-'),x=-
x;
if(x>
9)
out(x/
10);
putchar(x%
10+
'0');
}
int n;
LL ans=
0;
LL f[100010],sum[
100010];
struct node{
int a,b,c;
}tree[100010];
bool cmp(node x,node y){
return x.c<
y.c;
}
int getf(
int k){
if(f[k]==k)
return f[k];
return f[k]=
getf(f[k]);
}
int main(){
in(n);
REP(i,1,n-
1){
in(tree[i].a);
in(tree[i].b);
in(tree[i].c);
}
sort(tree+
1,tree+
n,cmp);
REP(i,1,n) sum[i]=
1,f[i]=
i;
REP(i,1,n-
1){
int x=getf(tree[i].a),y=
getf(tree[i].b);
if(x!=
y){
ans+=(sum[x]*sum[y]-
1)*(tree[i].c+
1)+
tree[i].c;
f[y]=
x;
sum[x]+=
sum[y];
// cout<<x<<" "<<y<<" "<<f[y]<<" "<<sum[x]<<" "<<ans<<endl;
}
}
cout<<
ans;
return 0;
}
转载于:https://www.cnblogs.com/jason2003/p/9636584.html
相关资源：构造欧拉图与找欧拉回路的算法
