codevs 2796 最小完全图
2024-10-19 06:28:03
题目描述 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 20001
using 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=;i<n;i++)
{
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
sum+=e[i].w;
}
sort(e+,e+n);
for(int i=;i<=n;i++) siz[i]=,fa[i]=i;
int r1,r2;
for(int i=;i<n;i++)
{
r1=find(e[i].u);
r2=find(e[i].v);
ans+=(1ll*siz[r1]*siz[r2]-)*(e[i].w+);
fa[r1]=r2;
siz[r2]+=siz[r1];
}
printf("%lld",ans+sum);
}
最新文章
- oracle--知识点汇总2---laobai
- java分享第七天-03(递归打印文件目录的树状结构)
- Angularjs directive
- linux系统安装jdk
- python笔记一
- [51NOD1230]幸运数(数位DP)
- PHP中的多态
- 图的遍历(DFS、BFS)
- 在world中批量调整图片的大小
- USACO Section 4.2 Drainage Ditches(最大流)
- ASP.NET路由
- 松瀚SN8P2501 定时器初始化程序--汇编源码
- 什么是MQTT协议?
- 手把手教你如何安装Pycharm——靠谱的Pycharm安装详细教程
- 阿里云ACA主要内容
- 在没联网环境下,启动tomcat出错
- eclipse与idea快捷键对比以及idea debug、git快捷键
- Windows-WMI 事件 ID 10或0x80041003 死机 解药
- redis 版的 hello world
- 解决QtCreator中文乱码
热门文章
- 02-JAVA 初始化
- jdbc 1.0
- Beta 阶段项目计划
- 【leetcode】215. Kth Largest Element in an Array
- 使用.bat文件运行ant的build.xml
- 对象库(UI MAP)
- jquery validate 一个注册表单的应用
- 查询出menupath字段中 出现 “- ";(横杆)大于3次的 记录
- Xor Sum HDU - 4825(01字典序板题)
- 给自己的小练习19-[kuangbin带你飞]专题九连通图