洛谷P2330 [SCOI2005]繁忙的都市——kruskal
2024-09-05 19:38:07
给一手链接 https://www.luogu.com.cn/problem/P2330
这道题实质就是最小生成树
TIPS:最小生成树不仅是整体权值最小,也是最大边最小
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int M=2e5+;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int n,m,ans;
struct node{int from,to,w;}e[M];
int cmp(node x,node y){return x.w<y.w;}
int f[M],T;
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int main(){
n=read(); m=read(); T=n;
for(int i=;i<=n;i++) f[i]=i;
for(int i=;i<=m;i++) e[i].from=read(),e[i].to=read(),e[i].w=read();
sort(e+,e++m,cmp);
for(int i=;i<=m&&T>;ans=i,i++){
int p=find(e[i].from),q=find(e[i].to);
if(p==q) continue;
f[p]=q; T--;
}
printf("%d %d\n",n-,e[ans].w);
return ;
}
最新文章
- LINQ系列:LINQ to SQL Group by/Having分组
- spring cron表达式
- Samsung I9103刷cm-10.1的方法
- centos7 安装mysql5.7.11注意事项
- Quartz.net Cron表达式
- Divide Two Integers 解答
- Android开发人员必知的开发资源
- MySQL的";旁门左道";用法总结
- 内核对象kobject和sysfs(1)——概述
- Python3——让我们像孩子一样的去看书
- 自学python之路(day4)
- tuxedo 提供buildserver命令编译服务器进程
- https及证书
- Tensorflow生成唐诗和歌词(下)
- JQUERY-定义-查找
- php7 教程
- [DPI][suricata] suricata 配置使用
- hdu 5735 Born Slippy 暴力
- UVA 10026 Shoemaker&#39;s Problem 鞋匠的难题 贪心+排序
- Node FS 读取文件中文乱码解决
热门文章
- P5444 [APIO2019]奇怪装置
- SSM商城系统开发笔记-配置01-web.xml
- Archlinux笔记本安装手记
- CentOS6.5系统解决中文乱码问题
- Linux 部署或升级openssh7.5p1
- Codeforces Round #595 (Div. 3) 题解
- windows 使用 git 客户端
- orm 查询数据库随机返回一条数据的解决办法用models.User.objests.all().order_by(&#39;?&#39;).first()
- orm中 如何模糊匹配某一年的用户和某一事时间段的用户
- 【HDOJ6616】Divide the Stones(构造)