图论之构造完全图

标题 2398: 
信息学奥赛一本通T1489-构造完全图

时间限定: 2s 内存限定: 192MB 提交: 16 办理: 9
标题形貌

对于完全图 G，如有且仅有一棵最小天生树为 T，则称完全图 G 是树 T 扩展出的。
给你一棵树 T，找出 T 能扩展出的边权和最小的完全图 G。
输入格式

第一行 N 体现树 T 的点数；
接下来 N−1 行三个整数 Si,Ti,Di ；形貌一条边（Si,Ti）权值为 Di ；
包管输入数据构成一棵树。
输特殊式

输出仅一个数，体现最小的完全图 G 的边权和。
样例输入

复制

2. 4  
3. 1 2 1  
4. 1 3 1  
5. 1 4 2

复制代码

样例输出

复制

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，否则就不满足最小天生树的唯一性。

2. #include<bits/stdc++.h>
3. using namespace std;
4. const int N=1e5+10;
5. int p[N];
6. int cnt[N];
7. long long ans;
8. struct edge{
9.     int a,b,w;
10.     bool operator<(edge&W){
11.         return w<W.w;
12.     }
13. }e[N];
14. int t;
15. int find(int x){
16.     if(x!=p[x]){
17.         p[x]=find(p[x]);
18.     }
19.     return p[x];
20. }
21. int main()
22. {
23.     cin>>t;
24.     for(int i=1;i<=t;i++){
25.         p[i]=i;
26.         cnt[i]=1;
27.     }
28.     for(int i=1;i<t;i++){
29.         int a,b,c;
30.         cin>>a>>b>>c;
31.         e[i].a=a,e[i].b=b,e[i].w=c;
32.     }
33.     sort(e+1,e+t);
34.     for(int i=1;i<t;i++){
35.         int a=e[i].a;
36.         int b=e[i].b;
37.         int c=e[i].w;
38.         int x=find(a);
39.         int y=find(b);
40.         if(x!=y){
41.             p[x]=y;
42.             ans+=(long long)(cnt[x]*cnt[y]-1)*(c+1);
43.             cnt[y]=cnt[x]+cnt[y];
44.             ans+=c;
45.         }
46.     }
47.     cout<<ans;
48. }

复制代码

123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金