【并查集】构造完全图
题目描述
最小生成树P.S.S在宿命的指引下找到了巫师Kismi。P.S.S希望Kismi能帮自己变成一个完全图。Kismi由于某些不可告人的原因,把这件事交给了你。
PS: 可以保证,这个最小生成树对于最后求出的完全图是唯一的。
输入
第一行N表示树T的点数。
接下来N-1行: Si, Ti, Di;描述一条边( Si,Ti)权值为 Di。
保证输入数据构成一棵树。
输出
一个数,表示最小的图G的边权和。
样例输入
4 1 2 1 1 3 1 1 4 2
样例输出
12
提示
对于100%的数据,N<=100 000,1<=Di<=100 000
题解
本题最重要的地方就是理解数组edge[i](名字乱取的不重要)的含义,edge[i]表示的是以i为源点相连的点的数量(包括i点本身).
对于当前最小生成树中的每一条边,从权值最小的开始,将第i条边的两个端点分为两个集合,f1 f2是两个端点的源头节点,集合中的点的数量就分别是edge[f1],edge[f2],要使两个集合完全连接所需要的边的数量=edge[f1]*edge[f2],除去已经连接的边,最后需要连接的数量就是edge[f1]*edge[f2]-1,因为最小生成树唯一,所以这些边的最小权值就是已连接的边的权值+1。总的长度就是(edge[f1]*edge[f2]-1)*(node[i].weight+1),然后将两个集合合并,点的数量相加(edge[f1]+=edge[f2])。
做题的时候别忘了每个结点的初始edge[i]都为1(只有本身),不要忘记加上最小生成树中的边的权值。
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
int n,father[200005];
long long int sum=0,edge[200005];
struct Node
{int x,y;double weight;
}node[250000];
bool cmp(Node x,Node y)
{return x.weight<y.weight;
}int find(int x)
{if(father[x]==x)return x;elsereturn father[x]=find(father[x]);
}
int main()
{cin>>n;for(int i=1;i<=n;i++){father[i]=i;edge[i]=1;}for(int i=1;i<n;i++){cin>>node[i].x>>node[i].y>>node[i].weight;sum+=node[i].weight;}sort(node+1,node+n,cmp);for(int i=1;i<n;i++){int f1=find(node[i].x);int f2=find(node[i].y);if(f1==f2)continue;sum+=(edge[f1]*edge[f2]-1)*(node[i].weight+1);father[f2]=f1;edge[f1]+=edge[f2];}cout<<sum<<endl;return 0;
}
更多推荐
【并查集】构造完全图
发布评论