poj3522

发表于 | 分类于

一道对于最小生成树算法的很不错的应用。

题目要求是给你一张图，求一棵树，要求其 最大边与最小边的差值 最小。

考虑kruskal算法，排序之后我们枚举最小界，然后每次构建最小生成树可以得到最大边，然后不断地更新答案就好了。

poj3522

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct dou{
    int x,y;
    int w;
}l[10004];
int fa[103];
bool cmp(dou x,dou y)
{
    return x.w<y.w;
}
int gef(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=gef(fa[x]);
}
int n,m;
int main()
{
    while((~scanf("%d%d",&n,&m))&&n)
    {
        for(int i=1;i<=m;i++)
            scanf("%d%d%d",&l[i].x,&l[i].y,&l[i].w);
        sort(l+1,l+1+m,cmp);
        int big=l[m].w;
        for(int i=1;i<=m;i++)
        {
            int j,k;
            for(j=1;j<=n;j++)
                fa[j]=j;
            for(j=i;j<=m;j++)
            {
                int x=gef(l[j].x);
                int y=gef(l[j].y);
                if(x!=y) 
                {
                    fa[x]=y;
                    k=j;
                }
            }
            int sum=0;
            for(int j=1;j<=n;j++)
            {
                fa[j]=gef(fa[j]);
                if(fa[j]==j)sum++;
            }
            if(sum!=1)break;
            big=min(big,l[k].w-l[i].w);
        }
        if(big==l[m].w)big=-1;
        printf("%d\n",big);
    }
    return 0;
}