不可以按照边权从大到小?
题意:在一个树中(最小生成树本树),添加若干边,使得这棵树变成一个完全图(图中任意两个顶点之间一定有边联通),然后这棵树仍然是唯一的最小生成树,添加边的权重自己决定,最终要求添加的边的总权重。
做法:按照边权从小到大遍历树中的边,除了当前这条边,其连接的左右两端都是相互连通的完全图。因此需要x*y的额外边才能拓展成完全图。
//当前树就是最小生成树 ,题目要求加边后仍然是唯一最小生成树
//按照边权大小枚举这棵树的边(此时看作还没有这条边),这条边两边连接的是两个完全连接的团,只有添加边的权重
//是wi+1才能保证最小生成树不变且唯一。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=6010,M=N*N/2;
int p[N],siz[N];
int n;
struct edge{
int a,b,w;
bool operator< (const edge &t) const{
return w<t.w;
}
}e[N];
int find(int x){
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
int main(){
int T;
cin>>T;
while(T--){
cin>>n;
for(int i=0;i<n-1;i++) {
int a,b,w;
cin>>a>>b>>w;
e[i]={a,b,w};
}
sort(e,e+n-1);
for(int i=1;i<=n;i++){
p[i]=i;
siz[i]=1;
}
int res=0;//res不会爆int的分析
for(int i=0;i<n-1;i++){
int a=find(e[i].a),b=find(e[i].b),w=e[i].w;
if(a!=b){
p[a]=b;
//已经有了树中自带的一条
res+=(siz[a]*siz[b]-1)*(w+1);
siz[b]+=siz[a];
}
}
cout<<res<<endl;
}
return 0;
}