UVA1395
2024-09-28 15:32:59
// UVa1395 Slim Span // Rujia Liu #include<cstdio> #include<cmath> #include<cstring> #include<vector> #include<algorithm> using namespace std; + ; ; int n; int pa[maxn]; int findset(int x) { return pa[x] != x ? pa[x] = findset(pa[x]) : x; } struct Edge { int u, v, d; Edge(int u, int v, int d):u(u),v(v),d(d) {} bool operator < (const Edge& rhs) const { return d < rhs.d; } }; vector<Edge> e; int solve() { int m = e.size(); sort(e.begin(), e.end()); int ans = INF; ; L < m; L++) { //枚举从第L条边开始kruskal ; i <= n; i++) pa[i] = i; int cnt = n; // number of sets for(int R = L; R < m; R++) { //枚举终点,遇到终止条件break int u = findset(e[R].u), v = findset(e[R].v); if(u != v) { pa[u] = v; ) { ans = min(ans, e[R].d-e[L].d); break; } //计算“苗条度” } } } ; return ans; } int main() { int m, u, v, d; && n) { e.clear(); ; i < m; i++) { scanf("%d%d%d", &u, &v, &d); e.push_back(Edge(u, v, d)); } printf("%d\n", solve()); } ; }
最新文章
- WangSql 1.0源码共享
- Linux(Centos)之安装tomcat并且部署Java Web项目
- iOS阶段学习第六天笔记(数组)
- Spark SQL External Data Sources JDBC官方实现写测试
- (转)Eclipse New Server 【无法输入server name】
- 中型企业的IT运维策略
- VS2008使用技巧及快捷键大全
- HashMap(JDK1.8)源码剖析
- [HMLY]2.CocoaPods详解----进阶
- C++------------typedef 函数指针类型定义
- factorOne cannot be&;nb…
- switch case异常处理机制
- jquery.i18n.properties前端国际化解决方案“填坑日记”
- 【BZOJ4816】数字表格(莫比乌斯反演)
- [BBS]搭建开源论坛之Jforum搭配开源CKEDITOR
- Orientation Auto Rotation旋转屏幕crash问题(Unity3D开发之十四)
- 国际空间站直播 ISS直播
- js可拖拽的div
- Main Steps to Setup an ODI data sync
- C语言内存四区的学习总结(三)---- 栈区