UVa 1395 - Slim Span

contents

1. 1. Problem
2. 2. Sample Input
3. 3. Sample Output
4. 4. Solution

Problem

找一個生成樹，使得最大邊與最小邊的差最小。

Sample Input

4 5 
1 2 3
1 3 5
1 4 6
2 4 6
3 4 7
4 6 
1 2 10 
1 3 100 
1 4 90 
2 3 20 
2 4 80 
3 4 40 
2 1 
1 2 1
3 0 
3 1 
1 2 1
3 3 
1 2 2
2 3 5 
1 3 6 
5 10 
1 2 110 
1 3 120 
1 4 130 
1 5 120 
2 3 110 
2 4 120 
2 5 130 
3 4 120 
3 5 110 
4 5 120 
5 10 
1 2 9384 
1 3 887 
1 4 2778 
1 5 6916 
2 3 7794 
2 4 8336 
2 5 5387 
3 4 493 
3 5 6650 
4 5 1422 
5 8 
1 2 1 
2 3 100 
3 4 100 
4 5 100 
1 5 50 
2 5 50 
3 5 50 
4 1 150 
0 0

Sample Output

1 
20 
0 
-1 
-1 
1 
0 
1686 
50

Solution

窮舉最小邊權重使用，使用 kruscal 找到瓶頸的最大邊。

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
struct E {
    int x, y, v;
    E(int a=0, int b=0, int c=0):
        x(a), y(b), v(c) {}
    bool operator<(const E &a) const {
        return  v < a.v;
    }
};
E D[10005];
int p[1005], rank[1005];
int findp(int x) {
    return p[x] == x ? x : (p[x] = findp(p[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], p[y] = x;
    else
        rank[y] += rank[x], p[x] = y;
    return 1;
}
int kruscal(int n, int m, E D[], int &max_edge) {
    max_edge = 0;
    for(int i = 0; i <= n; i++)
        p[i] = i, rank[i] = 1;
    int ee = 0;
    for(int i = 0; i < m; i++) {
        if(joint(D[i].x, D[i].y))
        	max_edge = max(max_edge, D[i].v), ee++;
    }
    return ee == n-1;
}
int main() {
    int n, m, x, y, w;
    while (scanf("%d %d", &n, &m) == 2 && n+m) {
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &w);
            D[i] = E(x, y, w);
        }
        sort(D, D+m);
        int ret = 0x3f3f3f3f, mxedge;
        for (int i = 0; i < m; i++) {
            if (kruscal(n, m-i, D+i, mxedge))
                ret = min(ret, mxedge - D[i].v);
            else
                break;
        }
        printf("%d\n", ret == 0x3f3f3f3f ? -1 : ret);
    }
    return 0;
}