POJ 3522 슬 림 스 판 (kruskal 변형)

제목:
그림 에서 나 무 를 생 성 하 는 가장 긴 변 과 가장 짧 은 변 의 차 이 를 최소 화 합 니 다.
생각:
1. 우선 모든 생 성 트 리 를 구 해 야 차이 의 최소 치 를 구 할 수 있다.
2. kruskal 알고리즘 을 이용 하여 작은 것 부터 큰 것 까지 정렬 한 다음 에 우 리 는 작은 것 부터 시작 하여 변 집 i ~ m 에서 생 성 할 수 있 는 나 무 를 매 거 합 니 다.
3. 나무 마다 길이 와 짧 은 변 의 차 이 를 최소 화하 면 됩 니 다.
 

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;



const int MAXN = 110;

const int INFS = 0x3FFFFFFF;



struct edge {

    int u, v, w;

    edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}

    bool operator < (const edge& o) { return w < o.w; }

};



vector<edge> edges;

int f[MAXN];



int find(int x) {

    int r = x;

    while (r != f[r])

        r = f[r];



    while (x != r) {

        int t = f[x];

        f[x] = r, x = t;

    }

    return r;

}



void merge(int a, int b) { f[a] = b; }



int kruskal(int n) {

    int ans = INFS;



    for (int i = 0; i < edges.size(); i++) {

        if (i + n - 1 > edges.size())

            break;



        for (int k = 1; k <= n; k++) 

            f[k] = k;

        int cflag = 0;

        for (int j = i; j < edges.size(); j++) {

            int ru = find(edges[j].u);

            int rv = find(edges[j].v);

            if (ru == rv) continue;

            merge(ru, rv);

            cflag += 1;

            if (cflag == n - 1) {

                ans = min(ans, edges[j].w - edges[i].w);

                break;

            }

        }

    }

    return ans == INFS ? -1 : ans;

}



int main() {

    int n, m;

    while (scanf("%d%d", &n, &m) && (n || m)) {

        edges.clear();

        for (int i = 0; i < m; i++) {

            int a, b, c;

            scanf("%d%d%d", &a, &b, &c);

            edges.push_back(edge(a, b, c));

        }

        sort(edges.begin(), edges.end());

        printf("%d
", kruskal(n));

    }

    return 0;

}