概念

  就和它的名字所说的一样，最短生成树满足以下两个条件：

  1. 它是一棵树
  2. 它满足最短

  首先，因为它是一棵树，所以其构成必然不可能形成环，如果有一颗 N个点构成的最小生成树，那么其一定有 N - 1条边。

  这里说的“最短”是什么意思呢？假设图中每条边都有一个权重，这个最短就是指的这 N - 1个边的权重之和最小。

对比最短路径

  最短生成树和最短路径是否有共同之处？答案肯定是有，两者都要求“最短”，但是两者的前提不同。 最短路径要求连接出来的是一条路径，或者说是一根线；而最短生成树是一棵树。也正因为如此，生成最短生成树要比生成最短路径要简单。

算法

  生成最短生成树主流的有两种算法：Kruskal和 Prim。

我们使用圆形表示节点，其中字母为节点编号，数字是节点所在的树的编号

  假设有如下的无向图：

无向图

Kruskal

  Kruskal算法以边为基础构建最短生成树：

  1. 记录所有边并按长度从小到大排序
  2. 记录每一个节点所在的树
  3. 取最短的一条边，如果边上的两点不在同一棵树中，那么合并这两棵树，否则跳过这一条边
  4. 重复 3直到连接了 N - 1个边

点信息存储

  首先，我们需要想办法记录哪一个节点属于哪一棵树，不难想到使用 map存储，但是有一个问题是如何合并两棵树？把所有节点都遍历一遍然后修改需要修改的节点吗？这个方案是可行的，但是未免太过复杂，同时性能表现也不太好。那应该如何处理呢？这时候我们就用到了并查集，使用并查集我们就可以快速地进行树合并操作。

  为了方便起见，我们规定以下两个函数：

  1. int find(int)：查找指定编号的点所属的树的编号
  2. void merge(int, int)：合并两个节点所在的树

并查集这里就不多说了

  合并两棵树的时候还可以使用一下启发式合并，这样的性能表现更优。不过在竞赛中，即使不使用启发式合并一般也不会T掉。

边信息存储

  接下来，我们要存储边地信息并排序。对于每一条边，我们需要存储两个信息：

  1. 边上地两个点是什么
  2. 边的权重是多少

  所以我们就可以采用下面这个结构体存储数据：

1
2
3
4
5
6
struct side {
    int head, tail, value;
    bool operator<(const side& that) const {
        return value < that.value;
    }
}

  特别需要注意的是，如果你使用 set存储输入的 side，那么就不能使用上面的这个比较大小的方法，因为 set中不允许元素重复，这样的比较方法会导致 head和 tail不同但是 value相同的边被判定为重复元素，所以我们应当使用下面的方法：

1
2
3
4
5
6
bool operator<(const side& that) const {
    if (value == that.value) {
        if (head == that.head) return tail < that.tail;
        else return head < that.head;
    } else return value < that.value;
}

  特别的，如果题目中可能出现两个点连接多个边的输入，那么上述的方法同样会出现问题。因为此时我们读入数据时需要以下操作：

  1. 查找输入的两个点间是否有连线
  2. 如果是则在已有数据和输入数据中保留最优的一个，否则插入数据

  仅使用上述方法很明显无法快速的实现上面的效果，因为我们需要手写查找方法而不能直接使用 set提供的 find。对此，我们使用下面的结构体就能解决问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
struct side {
    int head, tail, value;
    side() : side(-1, -1, 0) {}
    side(int _h, int _t, int _v) : head(min(_h, _t)), tail(max(_h, _t)), value(_v) {}
    bool operator<(const side& that) const {
        if (head == that.head) {
            if (tail == that.tail) return false;
            else if (value == that.value) return tail < that.tail;
            else return tail < that.tail;
        } else if (value == that.value) return head < that.head;
        else return value < that.value;
    }
}

  首先，这个结构体的构造函数保证了 head ≤ tail，简化了比较函数的代码。其次，专门编写的比较函数保证了在两个对象的 head和 tail都相等时一定返回 false。

  竞赛中到底要使用数组还是 set存储边信息要取决于具体情况，一般情况下哪一种方便使用哪一种即可。（当然不是必须用这两个，根据情况优先级队列什么的都是有可能可以使用的。）

  为了方便起见，我们假定使用side sideMap[]存储所有的边。

生成树

  现在我们需要的信息全部都存储下来了，接下来的任务就是生成树了。还记得我们前面提到的步骤吗？使用代码实现就长下面这样子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
list<side> createMST() {
    list<side> result;
    int index = 0;
    for (int i = 1; i != n;) {
        int head = find(sideMap[index].head);
        int tail = find(sideMap[index].tail);
        if (head != tail) {
            result.push_back(sideMap[index]);
            merge(head, tail);
            ++i;
        }
        ++index;
    }
    return result;
}

运行过程

点击查看运行过程（图片较多）
  • 黑色线：还未遍历
  • 红色线：丢弃的线
  • 紫色线：采用的线

注：为了作图方便，对于权重一样的线，按随机顺序选用

运行效果-1

运行效果-2

运行效果-3

运行效果-4

运行效果-5

运行效果-6

  这个样例没选好，导致前面N - 1条线全部都选用了，下次我注意

Prim

  Prim算法以点为基础构建树：

  1. 以任意一个点开始生成
  2. 计算其它点（即不在树中的点）距离树的距离
  3. 选择距离最短的点加入树中
  4. 重复2直到连接了所有的点

存储点信息

  在Prim算法中一个点有以下信息需要存储：

  1. 是否已经在树中
  2. 它连接了哪些点

  对于第一个非常好处理，直接使用bool数组、set或者map就可以了。

  至于一个点连接了哪些点的存储方式，我们也不多说了，可以参考图的存储。

存储边信息

  上面已经说过了，这里就不重复了。

点边合并存储

  采用Prim算法时，很多情况下我们可以合并点和边的信息，我们可以使用下面的这个结构体：

1
2
3
4
5
6
struct point {
    //连接的点编号
    int index;
    //两点距离（或者说是两点连线的权重）
    int value;
}

  很多人可能要疑惑了，对于一条边为什么我只存储了一个点？实际上这个结构体并不能自成结构，他需要外部记录另一个点是什么，这很简单，我们可以采用邻接表的形式存储（例如：list<point> sideMap[]），这样另一个点是什么就记录下来了。

最近点信息

  我们需要存储离树最近的点是什么，存储前我们肯定需要计算出来。计算方法很简单，如果已加入树的节点列表是set<int> treeMap，那么指定点A到树的距离就是A到数中所有点的距离的最小值。当然这个方法很明显是可以优化的，我们只需要在加入新的点时计算与加入的点相邻的点到树的距离即可。

  现在让我们来看有什么存储计算出来的信息的方法，如果我们以点编号为key，以点到树的距离为value，我们可以非常方便的将数据存储起来。那么我们如何读取数据呢？我们需要遍历所有参与计算的点的数据，然后找到其中value最小的，所以我们还需要存储我们计算了哪些点.

  当然还有其它的存储方法，比如使用优先级队列，每次寻找最优解时扔掉不能用的就行了。

生成树

注：这两个代码均没有经过测试，如果有问题还请告知

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
list<side> createMST() {
    set<int> treeMap;
    map<int, point> near; //与树直接相连的点的信息
    treeMap.insert(0);
    int last = 0;   //最新的添加进去的点
    list<side> result;
    for (int i = 1; i != n; ++i) {
        int& old = near[last];
        if (old == 0) old = INT_MAX;
        for (point node : sideMap[last]) {
            if (treeMap.find(node.index) != treeMap.end()) continue;
            old = min(old, node.value);
        }
        int next;
        point minValue = {0, INT_MAX};
        for (const auto& entry : near) {
            if (entry.second.value < minValue.value) {
                minValue = entry.second;
                next = entry.first;
            }
        }
        near.erase(next);
        treeMap.insert(next);
        result.emplace(next, minValue.index, minValue.value);
        last = next;
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//注：这里的side的head，tail不排序（head可以大于tail）
list<side> createMST() {
    set<int> treeMap;
    priority_queue<side, vector<side>, greater<side>> near; //与树直接相连的点的信息
    treeMap.insert(0);
    int last = 0;   //最新的添加进去的点
    list<side> result;
    for (int i = 1; i != n; ++i) {
        for (point node : sideMap[last]) {
            if (treeMap.find(node.index) != treeMap.end()) continue;
            near.emplace(last, node.index, node.value);
        }
        while (!near.empty()) {
            auto node = near.top();
            near.pop();
            if (treeMap.find(node.tail) != treeMap.end()) continue;
            result.push_back(node);
            treeMap.insert(node.tail);
            last = node.tail;
            break;
        }
    }
    return result;
}

运行过程

点击查看运行过程（图片较多）
  • 黑色线：未访问
  • 红色线：已计算长度
  • 紫色线：选用的线

运行效果-1

运行效果-2

运行效果-3

运行效果-4

运行效果-5

运行效果-6

例题

最小生成树

  给定结点数为n，边数为m的带权无向连通图G，所有结点编号为 1,2,…,n。

  求G的最小生成树的边权和。

输入格式

  第一行两个正整数n,m。

  之后的m行，每行三个正整数 ui, vi,wi（1 ≤ ui, vi ≤ n, 0 ≤ wi ≤ 109），描述一条连接结点ui和vi，边权为 wi的边。

输出格式

  一个整数表示G的最小生成树的边权和。

题解

  使用了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
struct side {
    int head, tail, value;
    side(int a, int b, int value) : head(min(a, b)), tail(max(a, b)), value(value) {}
    side() : side(-1, -1, -1) {}
    bool operator<(const side& that) const {
        if (value == that.value) {
            if (head == that.head) return tail < that.tail;
            else return head < that.head;
        } else return value < that.value;
    }
};

int n;
set<side> sideMap;
int pointMap[200001];

void merge(int a, int b) {
    pointMap[b] = a;
}

int find(int index) {
    if (index == pointMap[index]) return index;
    else return pointMap[index] = find(pointMap[index]);
}

long long solve() {
    long long result = 0;
    auto it = sideMap.begin();
    for (int i = 1; i != n;) {
        auto& node = *it;
        int head = find(node.head);
        int tail = find(node.tail);
        if (head != tail) {
            merge(head, tail);
            result += node.value;
            ++i;
        }
        ++it;
    }
    return result;
}

int main() {
    int m, a, b, value;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) pointMap[i] = i;
    while (m--) {
        scanf("%d %d %d", &a, &b, &value);
        sideMap.emplace(a, b, value);
    }
    cout << solve();
    return 0;
}

聪明的猴子

  在一个热带雨林中生存着一群猴子，它们以树上的果子为生。昨天下了一场大雨，现在雨过天晴，但整个雨林的地表还是被大水淹没着，部分植物的树冠露在水面上。猴子不会游泳，但跳跃能力比较强，它们仍然可以在露出水面的不同树冠上来回穿梭，以找到喜欢吃的果实。

  现在，在这个地区露出水面的有N棵树，假设每棵树本身的直径都很小，可以忽略不计。我们在这块区域上建立直角坐标系，则每一棵树的位置由其所对应的坐标表示(任意两棵树的坐标都不相同)。

  在这个地区住着的猴子有M个，下雨时，它们都躲到了茂密高大的树冠中，没有被大水冲走。由于各个猴子的年龄不同、身体素质不同，它们跳跃的能力不同。有的猴子跳跃的距离比较远(当然也可以跳到较近的树上)，而有些猴子跳跃的距离就比较近。这些猴子非常聪明，它们通过目测就可以准确地判断出自己能否跳到对面的树上。

  【问题】现已知猴子的数量及每一个猴子的最大跳跃距离，还知道露出水面的每一棵树的坐标，你的任务是统计有多少个猴子可以在这个地区露出水面的所有树冠上觅食。

输入格式

  第1行为一个整数，表示猴子的个数M(2 ≤ M ≤ 500)；

  第2行为M个整数，依次表示猴子的最大跳跃距离（每个整数值在1~1000之间）；

  第3行为一个整数表示树的总棵数N(2 ≤ N ≤ 1000)；

  第4行至第N + 3行为N棵树的坐标（横纵坐标均为整数，范围为：-1000~1000）。

  （同一行的整数间用空格分开）

输出格式

  输出包括一个整数，表示可以在这个地区的所有树冠上觅食的猴子数。

题解

  使用了Prim算法。

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
int jumpDis[500];
pair<int, int> treeMap[1000]; // NOLINT(cert-err58-cpp)

int distance(int a, int b) {
    int difX = treeMap[a].first - treeMap[b].first;
    int difY = treeMap[a].second - treeMap[b].second;
    double dis = sqrt(difX * difX + difY * difY);
    int result = int(dis) << 1;
    if (dis - int(dis) > 1e-6) ++result;
    return result;
}

int solve(int n) {
    typedef pair<int, int> info;
    bool check[1000]{true,};
    priority_queue<info, vector<info>, greater<info>> near;
    int last = 0;
    int result = 0;
    for (int i = 1; i != n; ++i) {
        for (int k = 1; k != n; ++k) {
            if (!check[k]) near.emplace(distance(last, k), k);
        }
        while (!near.empty()) {
            auto node = near.top();
            near.pop();
            if (check[node.second]) continue;
            check[node.second] = true;
            result = max(result, node.first);
            last = node.second;
            break;
        }
    }
    return result;
}

int main() {
    int m, n;
    cin >> m;
    for (int i = 0; i != m; ++i) {
        scanf("%d", &jumpDis[i]);
        jumpDis[i] <<= 1;
    }
    sort(jumpDis, jumpDis + m);
    cin >> n;
    for (int i = 0; i != n; ++i) {
        scanf("%d %d", &treeMap[i].first, &treeMap[i].second);
    }
    int maxDis = solve(n);
    int result;
    if (maxDis > jumpDis[m - 1]) result = 0;
    else {
        int index = int(upper_bound(jumpDis, jumpDis + m, maxDis) - jumpDis);
        if (index == m) result = m;
        else if (jumpDis[index - 1] == maxDis) result = m - index + 1;
        else result = m - index;
    }
    cout << result;
    return 0;
}

参考资料