MYF

UVa 1395 Slim Span

题目链接

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);

}
}