【OI考古】图论 | 最小生成树

2021-07-22

编程竞赛 (Competitive Programming)

OI考古

/

图论

/

C-C++

最小生成树（MST），顾名思义，对于带权无向连通图 $G$ ，其所有生成树中的权值和最小者 $T$ ，是其最小生成树。

模板题#

题目#

洛谷 P3366 | 【模板】最小生成树

题目描述#

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式#

第一行包含两个整数 $N,M$ ，表示该图共有 $N$ 个结点和 $M$ 条无向边。接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$ ，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$ 。

输出格式#

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz 。

输入输出样例#

输入#

输出#

说明/提示#

数据规模：

对于 $20\%$ 的数据， $N\le 5$ ， $M\le 20$ 。

对于 $40\%$ 的数据， $N\le 50$ ， $M\le 2500$ 。

对于 $70\%$ 的数据， $N\le 500$ ， $M\le 10^4$ 。

对于 $100\%$ 的数据： $1\le N\le 5000$ ， $1\le M\le 2\times 10^5$ ， $1\le Z_i \le 10^4$ .

样例解释：

所以最小生成树的总边权为 $2+2+3=7$ 。

Kruscal 算法#

思路#

Kruscal 算法是求 MST 的一种比较简单的方法，其核心思想是用贪心的思想构造 MST。

考虑图 $G$ 中权值最小的边 $e_1$ ，它一定在 MST 中。选中 $e_1$ 后，次小的边 $e_2$ ，它在 MST 中与 $e_1$ 在 MST 中不矛盾。以此类推，每次我们都考虑将未选边集中权值最小的边 $e_i$ 加入 MST。

然而不是所有这样的边都能加入 MST，因为 MST 毕竟还是一棵树，即无圈连通图，因此若 $e_i$ 连结的两个顶点 $u, v$ 已经包含在已选边集的生成子图中，则 $e_i$ 不能加入 MST。如此往复，直到加入 $n-1$ 条边，MST 构造完成。

为什么这样是正确的呢？我们注意到上述过程的的关键点是对于 $e_i$ ，如果 $e_i$ 连结的两个顶点 $u, v$ 已经包含在已选边集的生成子图中，则 $e_i$ 不加入 MST，其他部分都显然正确。只需要探讨不合法 $e_i$ 不加入的正确性即可。

对于 $e_i$ ，如果 $e_i$ 不合法，我们却想让它成为 MST 的一条边，则只需要将 $e_i$ 之前的某条边从 MST 中去掉即可，假设其为 $e_j$ ，但是显然 $e_i$ 的权值 $\ge$ $e_j$ ，结果会更差。故 $e_i$ 应该去掉。

代码#

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 5050;
const int maxm = 200500;
int n, m, ans;
int fa[maxn];
class Node
{
public:
    int u, v, w;
    bool operator<(const Node &b) const
    {
        return w < b.w;
    }

} E[maxm];

int getfa(int x)
{
    return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}

bool check(int x, int y)
{
    return getfa(x) == getfa(y);
}

void union_(int x, int y)
{
    fa[getfa(x)] = getfa(y);
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        E[i].u = u;
        E[i].v = v;
        E[i].w = w;
    }
    sort(E + 1, E + m + 1);
    for (int i = 1; i <= m; i++)
    {
        if (check(E[i].u, E[i].v))
            continue;
        ans += E[i].w;
        union_(E[i].u, E[i].v);
    }
    for (int i = 2; i <= n; i++)
    {
        if (getfa(i) != getfa(1))
        {
            printf("orz");
            return 0;
        }
    }
    printf("%d", ans);
    return 0;
}

解释#

为事先上述算法，我们需要先将边从小到大排序，每次检测 $e_i$ 两端的点 $u, v$ 在不在已选边集对应的点集内：如果不在，则将 $u$ 或 $v$ 加入该点集；如果在，则跳过这条边。检测点集的过程可以用并查集实现。