题目链接:

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();
}

最新文章

  1. VM环境下,快速复制多个SQLServer实例,环境调整
  2. LINQ to SQL语句(2)之Select/Distinct
  3. ndk学习9: 动态使用共享库
  4. 数据仓库与ODS的区别
  5. Nginx HA 及https配置部署
  6. YII千万级PV架构经验分享--俯瞰篇--架构即产品
  7. HTTP协议学习-02
  8. eclipse中使用git进行版本号控制
  9. Java R&amp;W Related
  10. mybatis 相关
  11. Maxwell入门
  12. 跟bWAPP学WEB安全(PHP代码)--认证绕过与会话管理
  13. 【.Net】在windows server 2016 和Windows10这些server上安装.net fw3.5
  14. Ng第十八课:应用实例:图片文字识别(Application Example: Photo OCR)
  15. java 高性能读模式(译)
  16. mysqli返回受影响行数
  17. Failed to add VMware DC to zone due to : This DC is being managed by other CloudStack deployment.
  18. quartz使用(整合spring)
  19. AES加密工具
  20. 幸运三角形 南阳acm491(dfs)

热门文章

  1. c#操作windows本地账户
  2. git命令行操作:拉不到最新代码???
  3. (转)如何使用caffe的MATLAB接口
  4. Android文件/文件夹选择器(支持多选操作),已封装为lib库,直接添加依赖即可。
  5. CEF和JS交互
  6. [转]显示农历日期的JS
  7. 小萝卜控机大师录制脚本(手机app自动化)
  8. Unity3D跨平台动态库编译---记kcp基于CMake的各平台构建实践
  9. node搭环境
  10. Could not find or load main class Hello