首页 > 代码库 > UVA 1395 - Slim Span(MST)
UVA 1395 - Slim Span(MST)
UVA 1395 - Slim Span
题目链接
题意:给定一些结点和边,要求出最苗条度最小的生成树,苗条度定义为:生成树中最大权的边减去最小权的边的值
思路:类似建最小生成树的算法,多一步枚举起始边即可
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 105; const int INF = 0x3f3f3f3f; int n, m, parent[N]; struct Edge { int u, v, val; Edge() {} Edge(int u, int v, int val) { this->u = u; this->v = v; this->val= val; } void read() { scanf("%d%d%d", &u, &v, &val); } } e[N * N]; int find(int x) { return x == parent[x] ? x : parent[x] = find(parent[x]); } bool cmp(Edge a, Edge b) { return a.val < b.val; } int main() { while (~scanf("%d%d", &n, &m) && n || m) { for (int i = 0; i < m; i++) e[i].read(); sort(e, e + m, cmp); int ans = INF; for (int i = 0; i < m; i++) { int cnt = 1; for (int j = 1; j <= n; j++) parent[j] = j; int flag = 1; for (int j = i; j < m; j++) { int u = find(e[j].u); int v = find(e[j].v); if (u != v) { parent[u] = v; cnt++; } if (cnt == n) { ans = min(ans, e[j].val - e[i].val); flag = 0; break; } } if (flag) break; } if (ans == INF) ans = -1; printf("%d\n", ans); } return 0; }
UVA 1395 - Slim Span(MST)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。