UVa1395 - Slim Span

思路

首先有一点是可以确定的:对于任何一连通图,必有一生成树(简直废话)。
对于这一题,关键的问题是确定最大与最小。对于这种寻找两个相关变量的题,其实一般可以先试着确定一个,然后再去寻找另一个。
比如在这题中,可以迭代每一个边 L,同时把这条边 L 当做最小的边,用比它大的边去试着连同一幅图,知道找到边 R, 使得加上这条边 R 后刚好可以凑成一幅联通图。
因此,从上述思路可以看出,排序是必不可少了。所有排序是第一步。
排序好后进行遍历 L,建立 N (顶点数) 个并查集 S,每加入一条边就将该边的端点对应的并查集合并(前提是两个端点对应不同的并查集)。
直到刚好加入边 R 后,并查集只剩一个,且大小刚好与顶点数相等。此时对于 L 来说,R - L 极为其 “苗条度”。
因此对所有求得的“苗条度”求一个最小值即可。如果连一个“苗条度”都没有,那结果自然就是找不到合适的答案了。

代码

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
/*
* Run Time : 0.033s
*/
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

struct Node{
int first, second;
int len;
};

bool cmp(Node a, Node b) {
return a.len < b.len;
}

const int INF = 1000000;
const int MAXN = 100 + 50;
int N, M;
vector<Node> nodes;
int size[MAXN], root[MAXN];

void read() {
int a, b, k;
nodes.clear();
for (int i = 0; i < M; ++ i) {
cin >> a >> b >> k;
Node n;
n.first = a; n.second = b; n.len = k;
nodes.push_back(n);
}
}

int ans;

int Find(int n) {
if (root[n] == n) {
return n;
}
return root[n] = Find(root[n]);
}

void work() {
sort(nodes.begin(), nodes.end(), cmp);
ans = INF;
for (int i = 0, j; i < M; ++ i) {
for (j = 1; j <= N; ++ j) {
size[j] = 1;
root[j] = j;
}
for (j = i; j < M; ++ j) {
int ra = Find(nodes[j].first);
int rb = Find(nodes[j].second);
if (ra != rb) {
root[rb] = ra;
size[ra] += size[rb];
}
if (size[Find(1)] == N) {
break;
}
}
if (size[Find(1)] == N) {
ans = min(nodes[j].len - nodes[i].len, ans);
} else if (size[Find(1)] < N) {
break;
}
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
while(cin >> N >> M && (N + M)) {
read();
work();
cout << (ans == INF ? -1 : ans) << endl;
}
return 0;
}

后记

最近没怎么练习,在做这题时犯了一个低级错误。刚开始使用了一个 set (集合)代替并查集。当 set 大小为 N 时,即可计算“苗条度”
这种想法当然是错误的!!!很明贤,顶点数达到要求了,但并不一定代表图已经连通!

LICENSED UNDER CC BY-NC-SA 4.0