图论之构造完全图

题目 2398: 

信息学奥赛一本通T1489-构造完全图

时间限制: 2s 内存限制: 192MB 提交: 16 解决: 9

题目描述

对于完全图 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

提示

样例说明

添加 D(2,3)=2,D(3,4)=3,D(2,4)=3 即可。

数据范围：

对于 20% 的数据，N≤10；

对于 50% 的数据，N≤1000；

对于 100% 的数据，N≤105,1≤Di≤105 。

 思路：

类似于kruskal建树过程，先找到最小树边，再在此基础上加边，使其成为一个局部完全图。依次进行，最后就得到一个最小权完全图。注意加边时边权应该为最小树边权加1，否则就不满足最小生成树的唯一性。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int p[N];
int cnt[N];
long long ans;
struct edge{int a,b,w;bool operator<(edge&W){return w<W.w;}
}e[N];
int t;
int find(int x){if(x!=p[x]){p[x]=find(p[x]);}return p[x];
}
int main()
{cin>>t;for(int i=1;i<=t;i++){p[i]=i;cnt[i]=1;}for(int i=1;i<t;i++){int a,b,c;cin>>a>>b>>c;e[i].a=a,e[i].b=b,e[i].w=c;}sort(e+1,e+t);for(int i=1;i<t;i++){int a=e[i].a;int b=e[i].b;int c=e[i].w;int x=find(a);int y=find(b);if(x!=y){p[x]=y;ans+=(long long)(cnt[x]*cnt[y]-1)*(c+1);cnt[y]=cnt[x]+cnt[y];ans+=c;}}cout<<ans;
}