POJ-2395 Out of Hay---MST最大边
2024-09-07 07:29:46
题目链接:
https://vjudge.net/problem/POJ-2395
题目大意:
求MST中的最大边,和POJ-2495类似
思路:
模板直接过
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<map>
#include<cmath>
using namespace std;
typedef pair<int, int> Pair;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int T, n, m;
const int maxn = 2e4 + ;
struct edge
{
int v, u, w;
bool operator < (const edge a)const
{
return w < a.w;
}
};
edge e[maxn];
int pa[maxn];
int Find(int x)
{
return x == pa[x] ? x : pa[x] = Find(pa[x]);//路径压缩
}
void kruskal()
{
for(int i = ; i <= n; i++)pa[i] = i;
sort(e, e + m);
int ans = ;
for(int i = ; i < m; i++)
{
int v = e[i].v, u = e[i].u, w = e[i].w;
int x = Find(v), y = Find(u);
if(x != y)
{
pa[x] = y;
ans = max(ans, w);
}
}
cout<<ans<<endl;
}
int main()
{
cin >> n >> m;
for(int i = ; i < m; i++)cin >> e[i].v >> e[i].u >> e[i].w;
kruskal();
}
最新文章
- VM环境下,快速复制多个SQLServer实例,环境调整
- LINQ to SQL语句(2)之Select/Distinct
- ndk学习9: 动态使用共享库
- 数据仓库与ODS的区别
- Nginx HA 及https配置部署
- YII千万级PV架构经验分享--俯瞰篇--架构即产品
- HTTP协议学习-02
- eclipse中使用git进行版本号控制
- Java R&;W Related
- mybatis 相关
- Maxwell入门
- 跟bWAPP学WEB安全(PHP代码)--认证绕过与会话管理
- 【.Net】在windows server 2016 和Windows10这些server上安装.net fw3.5
- Ng第十八课:应用实例:图片文字识别(Application Example: Photo OCR)
- java 高性能读模式(译)
- mysqli返回受影响行数
- Failed to add VMware DC to zone due to : This DC is being managed by other CloudStack deployment.
- quartz使用(整合spring)
- AES加密工具
- 幸运三角形 南阳acm491(dfs)