UVALive 3887 (暴力 并查集)

題意:求生成樹中最大邊-最小邊最小的值.

居然用n^4暴力過了還跑的飛快.邊排序之後枚舉最短的邊,然後每次往後加邊

一直加到隻剩下一個聯通分量就好了.

<strong>#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
using namespace std;
#define maxn 111
#define maxm maxn*maxn
#define INF 111111111

struct node {
    int u, v, w;
    bool operator < (const node &a) const {
        return w < a.w;
    }
}edge[maxm];
int n, m, fa[maxn];

int Find (int x) {
    return fa[x] == x ? fa[x] : fa[x] = Find (fa[x]);
}

void solve () {
    int ans = INF;
    for (int i = 1; i <= m; i++) {
        int cnt = n;
        for (int j = 1; j <= n; j++) fa[j] = j;
        for (int j = i; j <= m; j++) { 
            int p1 = Find (edge[j].u), p2 = Find (edge[j].v); 
            if (p1 != p2) {
                cnt--;
                fa[p1] = p2;
            }
            if (cnt == 1) {
                ans = min (ans, edge[j].w-edge[i].w);
                break;
            }
        }
        if (cnt != 1)
            break;
    }
    if (ans == INF) {
        printf ("-1\n");
    }
    else
        printf ("%d\n", ans);
}

int main () {
    while (scanf ("%d%d", &n, &m) == 2 && n+m) {
        for (int i = 1; i <= m; i++) {
            scanf ("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
        }
        sort (edge+1, edge+m+1);
        solve ();
    }
    return 0;
}
</strong>