首页 > 代码库 > 最大边和最小边之差最小的生成树 UVA 1394
最大边和最小边之差最小的生成树 UVA 1394
题目大意:给你n个点的图,求苗条度(最大边减最小编)尽量小的生成树
思路:sort以后暴力枚举区间即可
//看看会不会爆int!数组会不会少了一维!//取物问题一定要小心先手胜利的条件#include <bits/stdc++.h>using namespace std;#define LL long long#define ALL(a) a.begin(), a.end()#define pb push_back#define mk make_pair#define fi first#define se secondconst int inf = 0x3f3f3f3f;const int maxn = 100 + 5;struct Edge{ int u, v, val; Edge(int u = 0, int v = 0, int val = 0): u(u), v(v), val(val){} bool operator < (const Edge &a) const{ return val < a.val; }}edges[maxn * maxn];int par[maxn];int n, m;void init(){for (int i = 1; i <= n; i++) par[i] = i;}int pfind(int x){ if (par[x] == x) return x; return par[x] = pfind(par[x]);}bool solve(int l, int r){ for (int i = l; i <= r; i++){ int pu = pfind(edges[i].u); int pv = pfind(edges[i].v); if (pu == pv) continue; par[pu] = pv; } int p = pfind(1); for (int i = 2; i <= n; i++){ if (p != pfind(i)) return false; } return true;}int main(){ while (scanf("%d%d", &n, &m) && n){ for (int i = 1; i <= m; i++) { int u, v, val; scanf("%d%d%d", &u, &v, &val); edges[i] = Edge(u, v, val); } int ans = inf; sort(edges + 1, edges + m + 1); for (int l = 1; l <= m; l++){ init(); for (int r = l; r <= m; r++){ if (solve(l, r)){ ans = min(ans, edges[r].val - edges[l].val); break; } } } if (ans == inf) ans = -1; printf("%d\n", ans); } return 0;}
最大边和最小边之差最小的生成树 UVA 1394
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。