【最小生成树】BZOJ1682[Usaco2005 Mar]-Out of Hay 干草危机
2024-09-20 05:17:25
...最小生成树裸题,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 ;
}
最新文章
- 比官方教程代码更简短的SignalR Server Broadcast示例
- 第三方侧滑菜单SlidingMenu在android studio中的使用
- entity
- PHP 创建缩略图
- 为什么你不应该用angularjs?
- 开发者必读jQuery Mobile入门教程
- ajax。表单
- (转)ubuntu下如何查看和设置分辨率
- SRM 624 Building Heights DivI 解读
- redmine的邮件配置
- MVC5 DB FIRST
- maven 集成tomcat6,tomcat7
- 软工+C(5): 工具和结构化(重构中, part 1...)
- 微信小程序里如何用阿里云上传视频,图片。。
- HttpClient 知识点
- Python之父:为什么操作符很有用?
- [nodejs] nodejs开发个人博客(三)载入页面
- 大数据不就是写SQL吗?
- RPM安装MYSQL5.7
- docker之小记一