当前位置:网站首页>AcWing 1142. 繁忙的都市 题解(最小生成树)
AcWing 1142. 繁忙的都市 题解(最小生成树)
2022-07-06 18:00:00 【乔大先生】
AcWing 1142. 繁忙的都市
克鲁斯卡尔算法求最小生成树里最大的边,记录最后加入最小生成树内的边即可
#include<bits/stdc++.h>
using namespace std;
const int N = 8010;
struct Edge{
int a, b, w;
bool operator < (const Edge &t) const{
return w < t.w;
}
}e[N];
int p[N];
int n, m;
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
for(int i = 1; i <= n; i ++ ) p[i] = i;
for(int i = 0; i < m; i ++ ){
int a, b, c;
cin>>a>>b>>c;
e[i] = {
a, b, c};
}
sort(e, e + m);
int res = 0;
for(int i = 0; i < m; i ++ ){
int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
if(a != b){
p[a] = b;
res = w;
}
}
cout<<n - 1<<' '<<res<<endl;
return 0;
}
边栏推荐
- JTAG debugging experience of arm bare board debugging
- 负载均衡性能参数如何测评?
- 接收用户输入,身高BMI体重指数检测小业务入门案例
- 修改px4飞控的系统时间
- table表格设置圆角
- Body mass index program, entry to write dead applet project
- Match VIM from zero (0) -- Introduction to vimscript
- Google released a security update to fix 0 days that have been used in chrome
- 从零开始匹配vim(0)——vimscript 简介
- Let's see through the network i/o model from beginning to end
猜你喜欢
Make Jar, Not War
c语言—数组
golang中的Mutex原理解析
Transformation transformation operator
Start from the bottom structure to learn the customization and testing of fpga---- FIFO IP
云呐-工单管理制度及流程,工单管理规范
2022 Google CTF segfault Labyrinth WP
405 method not allowed appears when the third party jumps to the website
Typical problems of subnet division and super network construction
Body mass index program, entry to write dead applet project
随机推荐
1123. 最深叶节点的最近公共祖先
NEON优化:log10函数的优化案例
从零开始匹配vim(0)——vimscript 简介
C# 计算农历日期方法 2022
Installation of gazebo & connection with ROS
What are the differences between Oracle Linux and CentOS?
Add the applet "lazycodeloading": "requiredcomponents" in taro,
golang中的atomic,以及CAS操作
NEON优化:矩阵转置的指令优化案例
THREE.AxesHelper is not a constructor
Implementation principle of waitgroup in golang
The difference between spin and sleep
Spark TPCDS Data Gen
AI automatically generates annotation documents from code
WCF基金会
curl 命令
力扣1037. 有效的回旋镖
Dark horse notes - create immutable sets and streams
Match VIM from zero (0) -- Introduction to vimscript
交叉验证如何防止过拟合