首页 > 代码库 > codevs 2796 最小完全图
codevs 2796 最小完全图
2796 最小完全图
http://codevs.cn/problem/2796/
时间限制: 1 s
空间限制: 128000 KB
题目描述 Description
若一个图的每一对不同顶点都恰有一条边相连，则称为完全图。
最小生成树MST在Smart的指引下找到了你，希望你能帮它变成一个最小完全图（边权之和最小的完全图）。
注意：必须保证这个最小生成树MST对于最后求出的最小完全图是唯一的。
输入描述 Input Description
第一行一个整数n，表示生成树的节点数。
接下来有n-1行，每行有三个正整数，依次表示每条边的顶点编号和边权。
（顶点的边号在1-n之间，边权<231）
输出描述 Output Description
一个整数ans，表示以该树为最小生成树的最小完全图的边权之和。
样例输入 Sample Input
4
1 2 1
1 3 1
1 4 2
样例输出 Sample Output
12
数据范围及提示 Data Size & Hint
30%的数据：n<1000；
100%的数据：n≤20000，所有的边权<231。
因为题目输入时是一棵树，所以每一条边一定连接两个之前互不相交的点集
这两个点集 要保证这一条边是两点集间最小的边，且只有这一条，
所以其他的边都要至少比这条边大1
所以，将边从小到大排好序后，并查集
#include<cstdio>#include<algorithm>#define N 20001using namespace std;int n,siz[N],fa[N];long long ans,sum;struct node{ int u,v,w; bool operator < (node p) const { return w<p.w; }}e[N];int find(int i){ return fa[i]==i ? i:fa[i]=find(fa[i]);}int main(){ scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); sum+=e[i].w; } sort(e+1,e+n); for(int i=1;i<=n;i++) siz[i]=1,fa[i]=i; int r1,r2; for(int i=1;i<n;i++) { r1=find(e[i].u); r2=find(e[i].v); ans+=(1ll*siz[r1]*siz[r2]-1)*(e[i].w+1); fa[r1]=r2; siz[r2]+=siz[r1]; } printf("%lld",ans+sum);}
codevs 2796 最小完全图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。