首页 > 代码库 > 最大边和最小边之差最小的生成树 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;}
View Code

 

最大边和最小边之差最小的生成树 UVA 1394