首页 > 代码库 > 宿命的PSS

宿命的PSS

2024-10-10 23:40:39   216人阅读

题目描述

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

输入

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

输出

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

样例输入

3
1 2 4
2 3 7

样例输出

19

提示

 

n< 20000

 

 

这一道题目的意思就是给你一棵最小生成树的构造，求原来的完全图的总权值之和。那么有最小生成树的性质可知，我们选取的一定是最小的边，我们这一题最好使用克鲁斯卡尔，因为我们需要判断选取的点是否属于一个集合，如果不属于这个集合，按照道理来说，我们需要加入这个最小生成树，但是我们这里不能这么干，因为图中已经给出了真正的最小生成树，所以这一条边的权值是可以计算出来的。

 

技术分享 
 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 struct node
10 {
11     int u,v;
12     long long cost;    
13 };
14 
15 node a[100005];
16 int f[100005];
17 int N;
18 int Len=0;
19 long long d[100005];
20 
21 bool cmp(node i,node j)
22 {
23     return i.cost < j.cost;
24 }
25 
26 int find(int X)
27 {
28     if (f[X] != X) f[X]=find(f[X]);
29     return f[X];
30 }
31 
32 int main()
33 {
34     int M,K;
35     scanf("%d",&N);
36     for (int i=1; i<=N; i++)
37     {
38         f[i]=i;
39         d[i]=1;
40     }
41     for (int i=1; i<=N-1; i++)
42     {
43         scanf("%d%d%lld",&a[i].u,&a[i].v,&a[i].cost);
44     }
45     long long ans=0;
46     int total=0;
47     sort(a+1,a+N,cmp);
48     for (int i=1; i<=N-1; i++)
49     {
50         int fx=find(a[i].u);
51         int fy=find(a[i].v);
52         if (fx > fy) swap(fx,fy);
53         if (fx == fy) continue;
54         if (fx != fy)
55         {
56             f[fy]=fx;
57             ans+=(a[i].cost + 1) * d[fx] * d[fy];
58             d[fx]+=d[fy];
59         }
60     }
61     printf("%lld\n",ans - N + 1);
62 }
Show My Ugly Code

 

宿命的PSS


联系
我们