MYF

UVa 1395 Slim Span

Posted on | In | | Visitors

题目链接

UVa 1395

方法：最小生成树变形

题目分析

题目大意

给定n个点，m条边。对于任何一棵生成树，定义一个slimness，为最大边减最小边的值。问n个点m条边所形成的所有生成树中，最小的slimness

解析

几乎是模版题，用Kruskal先将所有边从小到大排序，然后先固定生成树的最小边，然后再确定其他边，搞一发即可。
不过时间非常长，建议再看看别人的码。

代码

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define PI acos(-1)
#define debug         printf("Hi----------\n")
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 10005
#define Vmax 200    //最大点数量
#define Emax 5000   //最大边数量
struct Kruskal{
    int n,m;//n个点 m条边
    int rank[Vmax],fa[Vmax];//并查集需要
    int weight;// weight为最小生成树的重量
    
    struct edge{
        int u,v,w;//起点 终点 权值
        bool operator<(const edge e) const{
            return w<e.w;
        }
    }e[Emax];
    
    Kruskal(int Vsz,int Esz):n(Vsz),m(Esz){};
    
    void init(){
        for(int i=0;i<=n;i++){
            fa[i]=i;
            rank[i]=0;
        }
    }
    
    //边的编号从0～m-1
    void adde(int id,int u,int v,int w){
        e[id].u=u;
        e[id].v=v;
        e[id].w=w;
    }
    
    int findx(int x){
        while(x!=fa[x])
            x=fa[x];
        return x;
    }
    
    void set_merge(int u,int v){
        if(rank[u]<rank[v]){
            fa[u]=v;
            rank[v]+=rank[u];
        }
        else{
            fa[v]=u;
            rank[u]+=rank[v];
        }
    }
    
    int kruskal(int start){
        int cnt=0;
        int mx=0;
        
        sort(e,e+m);
        int mn=e[start].w;
        
        for(int i=start;i<m;i++){
            int uR=findx(e[i].u);
            int vR=findx(e[i].v);
            if(uR!=vR){
                set_merge(uR, vR);
                mx=e[i].w;
                weight+=e[i].w;
                cnt++;
            }
        }
        if(cnt==n-1) return mx-mn;//最小生成树可建
        else return -1; //最小生成树不可建
    }
};
int main(){
    int n,m,u,v,w;
    while (scanf("%d%d",&n,&m),n) {
        int index=0,ans=INF;
        
        Kruskal tree(n,m);
        for (int i=0; i<m; i++) {
            scanf("%d%d%d",&u,&v,&w);
            tree.adde(index++, u, v, w);
        }
        
        for (int i=0; i<m; i++) {
            tree.init();
            int tmp=tree.kruskal(i);
            if (tmp!=-1) {
                ans=min(ans, tmp);
            }
        }
        
        if (ans==INF) {
            ans=-1;
        }
        printf("%d\n",ans);
        
    }
}