当前位置:网站首页>AcWing 1142. Busy urban problem solving (minimum spanning tree)
AcWing 1142. Busy urban problem solving (minimum spanning tree)
2022-07-07 01:36:00 【Mr. Qiao Da】
AcWing 1142. A busy city
Kruskal algorithm finds the largest edge in the minimum spanning tree , Record the last edge added to the minimum spanning tree
#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;
}
边栏推荐
- Gin 入门实战
- Receive user input, height BMI, BMI detection small business entry case
- LeetCode:1175. 质数排列
- AcWing 345. 牛站 题解(floyd的性质、倍增)
- 云呐|工单管理软件,工单管理软件APP
- Sword finger offer II 035 Minimum time difference - quick sort plus data conversion
- Your cache folder contains root-owned files, due to a bug in npm ERR! previous versions of npm which
- What are the differences between Oracle Linux and CentOS?
- Taro 小程序开启wxml代码压缩
- C language instance_ five
猜你喜欢
AcWing 345. 牛站 题解(floyd的性质、倍增)
2022 Google CTF SEGFAULT LABYRINTH wp
字节P7专业级讲解:接口测试常用工具及测试方法,福利文
黑马笔记---创建不可变集合与Stream流
LeetCode. 剑指offer 62. 圆圈中最后剩下的数
Dark horse notes - create immutable sets and streams
Body mass index program, entry to write dead applet project
一起看看matlab工具箱内部是如何实现BP神经网络的
Byte P7 professional level explanation: common tools and test methods for interface testing, Freeman
How to manage distributed teams?
随机推荐
字节P7专业级讲解:接口测试常用工具及测试方法,福利文
Yunna - work order management system and process, work order management specification
Js逆向——捅了【马蜂窝】的ob混淆与加速乐
HMM notes
table表格设置圆角
Amway wave C2 tools
2022 Google CTF SEGFAULT LABYRINTH wp
Transformation transformation operator
【信号与系统】
从零开始匹配vim(0)——vimscript 简介
Install Firefox browser on raspberry pie /arm device
Receive user input, height BMI, BMI detection small business entry case
搭建【Redis in CentOS7.x】
Gin 入门实战
Set up [redis in centos7.x]
Start from the bottom structure to learn the customization and testing of fpga---- FIFO IP
7.6模拟赛总结
从底层结构开始学习FPGA----FIFO IP的定制与测试
JS reverse -- ob confusion and accelerated music that poked the [hornet's nest]
mysqlbackup 还原特定的表