宿命的PSS

时间限制: 1 Sec 内存限制: 128 MB
提交: 60 解决: 37
[提交][状态][讨论版]

题目描述

最小生成树P.S.S在宿命的指引下找到了巫师Kismi。P.S.S希望Kismi能帮自己变成一个完全图。Kismi由于某些不可告人的原因，把这件事交给了你。 PS: 可以保证，这个最小生成树对于最后求出的完全图是唯一的。

输入

输入的第一行是一个整数n，表示生成树的节点数。接下来有n-1行，每行有三个正整数，依次表示每条边的端点编号和边权。（顶点的边号在1-n之间，边权< maxint）

输出

一个整数ans，表示以该树为最小生成树的最小完全图的边权之和。

样例输入

3 
1 2 4 
2 3 7

样例输出

提示

n< 20000

样例输入2：

1 2 1

1 3 1

样例输出2：

题解：可以用并查集祖先来记录该块的个数，然后连接两个块时计算需要加入的边的条数，然后乘以该最小生成树的边权+1这样即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<string>
 7 
 8 using namespace std;
 9 const int MAXN=20007;
10 
11 struct fzy
12 {
13     int u,v,zhi;
14 }a[MAXN];
15 struct xx
16 {
17     int anc,num;
18     void cc(int i)
19     {
20         anc=i;
21         num=1;
22     }
23 }f[MAXN];
24 
25 long long ans,sum;
26 int n;
27 
28 int find(int num)
29 {
30     if (f[num].anc!=num) f[num].anc=find(f[num].anc);
31     return f[num].anc;
32 }
33 bool cmp(fzy a,fzy b)
34 {
35     return a.zhi<b.zhi;
36 }
37 int main()
38 {
39     int x,y,z;
40     ans=0;
41     
42     scanf("%d",&n);
43     for (int i=1;i<=n;i++)
44         f[i].cc(i);
45     for (int i=1;i<n;i++)
46     {
47         scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].zhi);
48         sum+=a[i].zhi;
49     }
50     
51     sort(a+1,a+n,cmp);
52     
53     for (int i=1;i<n;i++)
54     {
55         x=find(a[i].u),y=find(a[i].v);
56         if (f[x].anc!=f[y].anc)
57         {
58             f[y].anc=f[x].anc;
59             ans+=(long long)((long long)f[x].num*f[y].num-1)*(a[i].zhi+1);
60             f[x].num+=f[y].num;
61         }
62     }
63     
64     ans+=sum;
65     printf("%lld",ans);
66 }

View Code