...最小生成树裸题,9月最后一天刷水刷水。

 #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXM=+;
const int MAXN=+;
struct Rec
{
int ori,des,len;
bool operator < (const Rec &x) const
{
return len<x.len;
}
}edge[MAXM];
int par[MAXN],height[MAXN];
int n,m;
int ans; void initset()
{
for (int i=;i<=n;i++)
{
par[i]=i;
height[i]=;
}
} int find(int x)
{
int r=x,temp;
while (par[r]!=r) r=par[r];
while (x!=r)
{
temp=par[x];
par[x]=r;
x=temp;
}
return (r);
} void unionset(int fa,int fb)
{
if (height[fa]>=height[fb])
{
par[fb]=fa;
if (height[fa]==height[fb]) height[fa]++;
}
else
par[fa]=fb;
} void init()
{
scanf("%d%d",&n,&m);
for (int i=;i<m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
edge[i].ori=u;
edge[i].des=v;
edge[i].len=w;
}
} void solve()
{
sort(edge,edge+m);
initset();
ans=;
for (int i=;i<m;i++)
{
int fa=find(edge[i].ori);
int fb=find(edge[i].des);
if (fa!=fb)
{
unionset(fa,fb);
ans=max(ans,edge[i].len);
}
}
printf("%d",ans);
} int main()
{
init();
solve();
return ;
}

最新文章

  1. 比官方教程代码更简短的SignalR Server Broadcast示例
  2. 第三方侧滑菜单SlidingMenu在android studio中的使用
  3. entity
  4. PHP 创建缩略图
  5. 为什么你不应该用angularjs?
  6. 开发者必读jQuery Mobile入门教程
  7. ajax。表单
  8. (转)ubuntu下如何查看和设置分辨率
  9. SRM 624 Building Heights DivI 解读
  10. redmine的邮件配置
  11. MVC5 DB FIRST
  12. maven 集成tomcat6,tomcat7
  13. 软工+C(5): 工具和结构化(重构中, part 1...)
  14. 微信小程序里如何用阿里云上传视频,图片。。
  15. HttpClient 知识点
  16. Python之父:为什么操作符很有用?
  17. [nodejs] nodejs开发个人博客(三)载入页面
  18. 大数据不就是写SQL吗?
  19. RPM安装MYSQL5.7
  20. docker之小记一

热门文章

  1. GD库imagecopyresampled()方法详解~
  2. [ JS 进阶 ] 闭包,作用域链,垃圾回收,内存泄露
  3. react CRA antd 按需加载配置 lessloader
  4. TinyOS 代码分析
  5. PEB及LDR链
  6. 如何优雅地使用vim编辑器
  7. Java的Timer定时器
  8. php直接输出json格式
  9. Linux上java环境变量配置
  10. 防范SQL注入