By yusijia

Updated:

Contents
  1. 1. 分析：

转：

分析：

　　题目要求的是找到一个生成树使得生成树中“最大边-最小边”的值最小。如果
这个图有n个点，那么这个生成树有n-1条边。那么现在就是考虑怎么去枚举这些生成
树，我们想到了跟边有关的就是kruskal。我们只要按照边的大小排好序，然后去枚举
最小的边的值，因为每一个生成树都要有n-1条边，所以只要枚举从0～(m-n+1)即可，然
后按照求解最小生成树的方法去求每一个生成树，最后求出ans。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 10000
#define INF 0x3f3f3f3f

int n , m , flag;
int father[MAXN];
int ranks[MAXN];
struct Edge{
    int x;
    int y;
    int value;
}edge[MAXN];

bool cmp(Edge e1, Edge e2)
{
    return e1.value < e2.value;
}

void init_set()
{
    for(int i = 1; i <= n; i++){
        father[i] = i;
        ranks[i] = 1;
    }
}

int find_set(int x)
{
    return x == father[x] ? father[x] : father[x] = find_set(father[x]);
}

void union_set(int x, int y)
{
    if(ranks[x] >= ranks[y]){
        ranks[x] += ranks[y];
        father[y] = x;
    }
    else{
        ranks[y] += ranks[x];
        father[x] = y;
    }
}

bool judge()//判断是否是最小生成树
{
    int x = find_set(1);
    if(ranks[x] == n)
        return true;
    else
        return false;
}

void kruskal()
{
    int maxs, mins;
    int ans = INF;
    flag = 0;
    sort(edge, edge + m, cmp);				//每个最小生成树都有n-1条边
    for(int i = 0; i <= m - n + 1; i++){  //n个点，m条边选定的最小边的范围是[0,m-(n-1)]
        init_set();//初始化
        maxs = 0;
        mins = INF;
        for(int j = i; j < m; j++){
            int root_x = find_set(edge[j].x);
            int root_y = find_set(edge[j].y);
            if(root_x != root_y){
                union_set(root_x, root_y);
                if(maxs < edge[j].value)
                    maxs = edge[j].value;
                if(mins > edge[j].value)
                    mins = edge[j].value;
            }
        }
        if(judge()){
            ans = ans < (maxs - mins) ? ans : (maxs - mins);
            flag = 1;
        }
    }
    if(flag)
        printf("%d\n", ans);
    else
        printf("-1\n");
}

int main()
{
    while(scanf("%d%d", &n, &m) != EOF && n + m){
        for(int i = 0; i < m; i++){
            scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].value);
        }
        kruskal();
    }
    return 0;
}
Contents
  1. 1. 分析：