UVa1395 - Slim Span

技术与工作
1.8k words

思路

首先有一点是可以确定的：对于任何一连通图，必有一生成树（简直废话）。
对于这一题，关键的问题是确定最大与最小。对于这种寻找两个相关变量的题，其实一般可以先试着确定一个，然后再去寻找另一个。
比如在这题中，可以迭代每一个边 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 时，即可计算“苗条度”
这种想法当然是错误的！！！很明贤，顶点数达到要求了，但并不一定代表图已经连通！