最小生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 $n$ ，则它的生成树含有 $n-1$ 条边。对生成树而言，若砍去一条边，则会变成非连通图，若加上一条边则会形成一个回路。

一个图的生成树可能有多个，将所有生成树中权值之和最小的树称为最小生成树。

构造最小生成树有多种算法，典型的有普利姆 ( Prim ) 算法和克鲁斯卡尔 ( Kruskal ) 算法两种，它们都是基于贪心的策略。关于正确性的证明，详细见《算法导论》中的讲解，这里的重点是模板的使用。

最小生成树的prim算法

核心：不断加点。

Prim 算法构造最小生成树的基本思想：

1. 从任意一个点开始构造最小生成树；

2. 贪心策略：将距离该树权值最小且不在树中的顶点，加入到生成树中。然后更新与该点相连的点到生成树的最短距离；

3. 重复 2 操作 $n$ 次，直到所有顶点都加入为止。

P3366 最小生成树 - 洛谷 邻接矩阵实现

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

这题只需要带出最小权值和。题目带有大量的重边，需要在读取数据时进行筛选。

OJ 参考程序兼 prim 算法模板：

#include <bits/stdc++.h>
using namespace std;
using std::vector;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using spii = set<pair<int, int>>;

int prim(vvi &pct, int n) {
    vi dist(n + 1, 0x3f3f3f3f); // 每个点离MST最小的距离
    vb vis(n + 1, 0);           // 记录该点是否是MST的结点
    int mst = 0;                // MST的权值
    dist[1] = 0;                // 更新 1 号点

    for (int tmpn = n; tmpn; tmpn--) {
        // 选择距离生成树最小的点
        int newp = 0; // 新加入树的点( new point )
        for (int i = 1; i <= n; i++) {
            if (vis[i])
                continue;
            if (newp == 0 || dist[newp] > dist[i])
                newp = i;
        }
        // 这个图不是所有点都连通
        if (dist[newp] == 0x3f3f3f3f)
            return 0x3f3f3f3f;
        // 更新mst的值
        vis[newp] = 1;
        mst += dist[newp];
        // 更新点与生成树的距离
        for (int i = 1; i <= n; i++) {
            // if (pct[newp][i] == 0) // 新加入的点和i点无连通
            //     continue;
            dist[i] = min(dist[i], pct[newp][i]);
        }
    }
    return mst;
}

int main() {
    int n, m;
    int ans = 0;
    vvi pct;
    cin >> n >> m;
    pct.resize(n + 1, vi(n + 1, 0x3f3f3f3f));
    for (int i = 1, x, y, z; i <= m; i++) {
        cin >> x >> y >> z;
        // 防止图有重边的情况
        pct[x][y] = pct[y][x] = min(pct[x][y], z);
    }
    if ((ans = prim(pct, n)) < 0x3f3f3f3f)
        cout << ans;
    else
        cout << "orz";
    return 0;
}

需要将最小生成树模型求出来的版本参考：

using std::vector;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using spii = set<pair<int, int>>;

int prim(vvi pct, spii &st, int n) {
    vi dist(n + 1, 0x3f3f3f3f), // 每个点离MST最小的距离
        edge(n + 1, 0);         // 记录每条边的关系
    vb vis(n + 1, 0);           // 记录该点是否是MST的结点
    int mst = 0;                // MST的权值
    dist[1] = 0;                // 更新 1 号点

    for (int tmpn = n; tmpn; tmpn--) {
        // 选择距离生成树最小的点
        int newp = 0; // 新加入树的点( new point )
        for (int i = 1; i <= n; i++) {
            if (vis[i])
                continue;
            if (newp == 0 || dist[newp] > dist[i])
                newp = i;
        }
        if (dist[newp] == 0x3f3f3f3f)
            return 0x3f3f3f3f;
        // 更新mst的值
        vis[newp] = 1;
        mst += dist[newp];
        // 将新生成的点加入最小生成树
        if (edge[newp] != 0) {
            int x = min(edge[newp], newp);
            int y = max(edge[newp], newp);
            st.insert(pair<int, int>(x, y));
        }
        // 更新点与生成树的距离
        for (int i = 1; i <= n; i++) {
            if (vis[i])
                continue;
            if (pct[newp][i] == 0) // 新加入的点和i点无连通
                continue;
            if (dist[i] > pct[newp][i]) { // 若不求最小生成树可直接用min
                dist[i] = pct[newp][i];
                edge[i] = newp;
            }
        }
    }
    return mst;
}

最小生成树 邻接表实现

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

邻接表实现的话，就不需要考虑重边的问题，只需要在更新 dist 数组时使用 min 运算即可。

参考程序兼模板：

#include <bits/stdc++.h>
using namespace std;
using std::vector;
using vi = vector<int>;
using vpii = vector<pair<int, int>>;
using vvi = vector<vi>;
using vvpii = vector<vpii>;
using vb = vector<bool>;

int prim(vvpii &pct, int n) {
    vi dist(n + 1, 0x3f3f3f3f);
    vb vis(n + 1, 0);
    int mst = 0;
    dist[1] = 0;
    for (int tmpn = 1; tmpn <= n; tmpn++) {
        int newp = 0;
        for (int i = 1; i <= n; i++) {
            if (vis[i])
                continue;
            if (newp == 0 || dist[newp] > dist[i])
                newp = i;
        }
        if (dist[newp] == 0x3f3f3f3f)
            return 0x3f3f3f3f;
        vis[newp] = 1;
        mst += dist[newp];
        for (auto &x : pct[newp])
            dist[x.first] = min(dist[x.first], x.second);
    }
    return mst;
}

int main() {
    int n, m, ans = 0;
    vvpii pct; // 邻接表存储
    cin >> n >> m;
    pct.resize(n + 1);
    for (int i = 1, x, y, z; i <= m; i++) {
        cin >> x >> y >> z;
        pct[x].push_back({y, z});
        pct[y].push_back({x, z});
    }
    if ((ans = prim(pct, n)) < 0x3f3f3f3f)
        cout << ans;
    else
        cout << "orz";
    return 0;
}

最小生成树 链式前向星实现

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

这里对链式前向星进行封装。链式前向星的 Prim 算法实现和邻接表的差不多，无非就是遍历方式的差别。

#include <bits/stdc++.h>
using namespace std;

// 链式前向星
using vb = vector<bool>;
using vi = vector<int>;
struct Pct {
    struct Node {
        int e;  // 权值
        int w;  // 边
        int ne; // 链表结点指针域
    };
    using VN = vector<Node>;
    vi h;  // 哨兵卫结点
    VN vn; // 单链表结点

    Pct() {
        vn.resize(1); // 防止链表遍历出错
    }
    int &operator[](const int &aim) { // 直接访问链表
        return h[aim];
    }
    void add(int a, int b, int c) { // 单链表头插
        vn.push_back(Node());       // 插入匿名对象
        int end = vn.size() - 1;
        vn[end] = {b, c, h[a]};
        h[a] = end;
    }
};

int prim(Pct &pct, int n) {
    vi dist(n + 1, 0x3f3f3f3f);
    vb vis(n + 1, 0);
    int mst = 0;
    dist[1] = 0;
    for (int tmpn = 1; tmpn <= n; tmpn++) {
        int newp = 0;
        for (int i = 1; i <= n; i++) {
            if (vis[i])
                continue;
            if (newp == 0 || dist[newp] > dist[i])
                newp = i;
        }
        if (dist[newp] == 0x3f3f3f3f)
            return 0x3f3f3f3f;
        vis[newp] = 1;
        mst += dist[newp];
        for (int i = pct[newp]; i; i = pct.vn[i].ne) // 遍历单链表
            dist[pct.vn[i].e] = min(dist[pct.vn[i].e], pct.vn[i].w);
    }
    return mst;
}

int main() {
    int n, m, ans = 0;
    Pct pct;
    cin >> n >> m;
    pct.h.resize(n + 1, 0);
    for (int i = 1, x, y, z; i <= m; i++) {
        cin >> x >> y >> z;
        pct.add(x, y, z);
        pct.add(y, x, z);
    }
    if ((ans = prim(pct, n)) < 0x3f3f3f3f)
        cout << ans;
    else
        cout << "orz";
    return 0;
}

最小生成树 prim算法堆优化方案

之前的 prim 算法，每次都需要遍历 dist 数组找离生成树最近的结点。

为减少查询的时间复杂度，引入堆来管理每个结点和树之间的距离。同时为避免不必要的判断，只有 dist 数组更新时，边的数据才会插入堆中。

这种堆优化的 prim 算法不适用于邻接矩阵存储的图，因为更新 dist 数组的复杂度并没有减小，优化不明显。但邻接表和链式前向星就很适合这种方案。

P3366 【模板】最小生成树 - 洛谷 邻接表实现：

#include <bits/stdc++.h>
using namespace std;
using std::vector;
using vi = vector<int>;
using vpii = vector<pair<int, int>>;
using vvi = vector<vi>;
using vvpii = vector<vpii>;
using vb = vector<bool>;
using pii = pair<int, int>;

int prim(vvpii &pct, int n) {
    vi dist(n + 1, 0x3f3f3f3f);
    vb vis(n + 1, 0);
    int mst = 0, tmpn = 0;
    priority_queue<pii, vpii, greater<pii>> pq;

    dist[1] = 0;
    pq.push({0, 1}); // {点到树的距离，点编号}
    while (!pq.empty()) {
        pii tp = pq.top();
        pq.pop();
        if (vis[tp.second])
            continue;
        ++tmpn; // 统计生成树的结点数
        vis[tp.second] = 1;
        mst += tp.first;
        // 松弛操作
        for (auto &x : pct[tp.second])    // 遍历邻接表
            if (x.second < dist[x.first]) // 这里的键值对的含义和堆不同
                dist[x.first] = x.second, pq.push({x.second, x.first});
    }
    if (tmpn < n)
        mst = 0x3f3f3f3f;
    return mst;
}

int main() {
    int n, m, ans = 0;
    vvpii pct; // 邻接表存储
    cin >> n >> m;
    pct.resize(n + 1);
    for (int i = 1, x, y, z; i <= m; i++) {
        cin >> x >> y >> z;
        pct[x].push_back({y, z});
        pct[y].push_back({x, z});
    }
    if ((ans = prim(pct, n)) < 0x3f3f3f3f)
        cout << ans;
    else
        cout << "orz";
    return 0;
}

P3366 【模板】最小生成树 - 洛谷 链式前向星实现：

#include <bits/stdc++.h>
using namespace std;

// 链式前向星
using vb = vector<bool>;
using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
struct Pct {
    struct Node {
        int e;  // 权值
        int w;  // 边
        int ne; // 链表结点指针域
    };
    using VN = vector<Node>;
    vi h;  // 哨兵卫结点
    VN vn; // 单链表结点

    Pct() {
        vn.resize(1); // 防止链表遍历出错
    }
    int &operator[](const int &aim) { // 直接访问链表
        return h[aim];
    }
    void add(int a, int b, int c) { // 单链表头插
        vn.push_back(Node());       // 插入匿名对象
        int end = vn.size() - 1;
        vn[end] = {b, c, h[a]};
        h[a] = end;
    }
};

int prim(Pct &pct, int n) {
    vi dist(n + 1, 0x3f3f3f3f);
    vb vis(n + 1, 0);
    int mst = 0;
    int tmpn = 0;
    priority_queue<pii, vpii, greater<pii>> pq;

    dist[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        if (tmpn >= n)
            break;
        pii tp = pq.top();
        pq.pop();
        if (vis[tp.second])
            continue;
        tmpn++; // 统计加入生成树的点的个数
        vis[tp.second] = 1;
        mst += tp.first;
        // 还是遍历方式不同
        for (int i = pct[tp.second]; i; i = pct.vn[i].ne) {
            if (pct.vn[i].w < dist[pct.vn[i].e])
                dist[pct.vn[i].e] = pct.vn[i].w,
                pq.push({pct.vn[i].w, pct.vn[i].e});
        }
    }
    if (tmpn < n)
        mst = 0x3f3f3f3f;
    return mst;
}

int main() {
    int n, m, ans = 0;
    Pct pct;
    cin >> n >> m;
    pct.h.resize(n + 1, 0);
    for (int i = 1, x, y, z; i <= m; i++) {
        cin >> x >> y >> z;
        pct.add(x, y, z);
        pct.add(y, x, z);
    }
    if ((ans = prim(pct, n)) < 0x3f3f3f3f)
        cout << ans;
    else
        cout << "orz";
    return 0;
}

最小生成树的kruskal算法

kruskal 算法的实现相对于 prim 算法来说比较简单，不容易出错。若时间复杂度和空间复杂度允许，建议使用 kruskal 算法。

核心：不断加边。

Kruskal 算法构造最小生成树的基本思想：

1. 所有边按照权值排序；

2. 贪心策略：每次选出权值最小且两端顶点不连通的一条边，直到所有顶点都联通。
   

kruskal 不用考虑如何建树，而是对边进行操作，整体使用并查集来实现。

P3366 最小生成树 - 洛谷

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

kurskal 算法实现：

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int s; // start边的起点
    int e; // end边的终点
    int w; // weight边的权值
    bool operator<(const Edge &aim) const {
        return w < aim.w;
    }
};
using Ve = vector<Edge>;
using vi = vector<int>;

int find(vi &f, int x) {
    return x == f[x] ? f[x] : find(f, f[x]);
}

int kruskal(Ve &ve, int n, int m) {
    vi f(n + 1, 0);
    int mst = 0, cnt = 0;

    for (int i = 0; i < f.size(); i++) // 初始化并查集
        f[i] = i;
    sort(ve.begin() + 1, ve.end()); // 对边排序
    for (int i = 1, fx, fy; i <= m; i++) {
        fx = find(f, ve[i].s), fy = find(f, ve[i].e);
        if (fx != fy) {
            ++cnt;
            mst += ve[i].w;
            f[fx] = fy;
        }
    }
    return cnt == n - 1 ? mst : 0x3f3f3f3f;
}

int main() {
    Ve ve;
    int n, m, ans = 0;
    cin >> n >> m;
    ve.resize(m + 1, {0, 0, 0});
    for (int i = 1; i <= m; i++)
        cin >> ve[i].s >> ve[i].e >> ve[i].w;
    if ((ans = kruskal(ve, n, m)) < 0x3f3f3f3f)
        cout << ans;
    else
        cout << "orz";
    return 0;
}

并查集的路径压缩还可用非递归实现：

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int s; // start边的起点
    int e; // end边的终点
    int w; // weight边的权值
    bool operator<(const Edge &aim) const {
        return w < aim.w;
    }
};
using Ve = vector<Edge>;
using vi = vector<int>;

int kruskal(Ve &ve, int n, int m) {
    vi f(n + 1, 0);
    int mst = 0, cnt = 0;
    auto find = [&](int x) {
        stack<int> sk;
        sk.push(x);
        while (f[x] != x) {
            sk.push(f[x]);
            x = f[x];
        }
        while(!sk.empty()){
            f[sk.top()] = x;
            sk.pop();
        }
        return x;
    };

    for (int i = 0; i < f.size(); i++) // 初始化并查集
        f[i] = i;
    sort(ve.begin() + 1, ve.end()); // 对边排序
    for (int i = 1, fx, fy; i <= m; i++) {
        fx = find(ve[i].s), fy = find(ve[i].e);
        if (fx != fy) { // 将边进行合并
            ++cnt;      // 统计加入生成树的边的个数
            mst += ve[i].w;
            f[fx] = fy;
        }
    }
    return cnt == n - 1 ? mst : 0x3f3f3f3f;
}

int main() {
    Ve ve;
    int n, m, ans = 0;
    cin >> n >> m;
    ve.resize(m + 1, {0, 0, 0});
    for (int i = 1; i <= m; i++) // 仅需存储边即可
        cin >> ve[i].s >> ve[i].e >> ve[i].w;
    if ((ans = kruskal(ve, n, m)) < 0x3f3f3f3f)
        cout << ans;
    else
        cout << "orz";
    return 0;
}

P1194 买礼物 - 洛谷 多个生成树

P1194 买礼物 - 洛谷

促销活动是买了一对物品中的一个，则只需要再付一定的价钱，就能获得另一个，而不是傻傻地付 2*A 的价钱买 2 个。

两个物品和它们的促销关系可构成一条带权值的边，多个这样的边就能组成一个图。因此买下所有的物品，相当于构建了这个图的最小生成树并求出了权值和。

但和原始的最小生成树相比有一些细节不同：

1. 促销活动关系是买了一个，只需要再付一定的价钱，就能获得另一个。因此得到了最小生成树的权值和还不够，还要再支付这个树上的任一结点的权值。
2. 这个图可能不是完全连通，而是分成多个彼此独立的子图，每个子图都有各自的最小生成树。所以答案是所有最小生成树的权值和，加上生成树的数量乘结点的权值。

因此使用 prim 算法和 kruskal 算法都能解决这个问题，只需要根据边的情况确定生成树的数量即可。若一个图的所有结点都连接生成一个最小生成树的话，边的数量是结点数量减1 ( $n-1$ ) ，每减少一个结点，生成树的数量都会增加 1 。所以生成树的数量就是这个图的结点数量减去形成最小生成树用掉的边的数量。

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int s;
    int e;
    int w;
    bool operator<(const Edge &aim) const {// 用于按权值排序
        return w < aim.w;
    }
};
using Ve = vector<Edge>;
using vi = vector<int>;

int kruskal(Ve &ve, int n, int &cnt) {
    int mst = 0;
    vi fa(n + 1, 0);
    auto find = [&](int x) { // 路径压缩
        vi sk(1, x);
        while (fa[x] != x) {
            sk.push_back(fa[x]);
            x = fa[x];
        }
        for (auto &y : sk)
            fa[y] = x;
        return x;
    };

    for (int i = 1; i <= n; i++) // 初始化并查集
        fa[i] = i;
    sort(ve.begin(), ve.end());
    for (auto &x : ve) {
        int fx = find(x.s), fy = find(x.e);
        if (fx != fy) {
            mst += x.w;
            ++cnt;
            fa[fx] = fy;
        }
    }
    return mst;
}

int main() {
    int A, B; // B个物品，每个都是A元
    int ans = 0, cnt = 0;
    Ve ve;
    cin >> A >> B;
    for (int i = 1, x; i <= B; i++) {
        for (int j = 1; j <= B; j++) {
            cin >> x;
            if (i < j && x && x < A)// 买了一对物品的其中一个，再付x的价格就能买下另一个
                ve.push_back({i, j, x});
        }
    }
    ans = kruskal(ve, B, cnt);
    cout << ans + (B - cnt) * A;
    return 0;
}

P2330 繁忙的都市 - 洛谷 瓶颈生成树

[P2330 SCOI2005] 繁忙的都市 - 洛谷

交叉路口是和其他交叉路口有道路连接的路口，在图论中可看成一个结点。分值可看成图的边权值，根据这些信息可得到一个图。

题目要求把所有的交叉路口连接起来，道路尽可能少，分值尽可能小，说的是求城市路线图的最小生成树。

但题目要求的并不是最小权值和，而是最小生成树的边数和权值最大的用于构造最小生成树的边的权值。可用 kluskal 算法解决，其中要求的 2 个值可在并查集的子树合并时统计。

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int s;
    int e;
    int w;
    bool operator<(const Edge &aim) const {
        return w < aim.w;
    }
};
using vE = vector<Edge>;
using vi = vector<int>;

void kruskal(vE &ve, int n, int &edge_num, int &maxx) {
    vi fa(n + 1, 0);
    auto find = [&fa](int x) {
        vi sk(1, x);
        while (x != fa[x]) {
            sk.push_back(fa[x]);
            x = fa[x];
        }
        for (auto &y : sk)
            fa[y] = x;
        return x;
    };
    
    for (int i = 0; i < fa.size(); i++)
        fa[i] = i;
    sort(ve.begin(), ve.end());
    for (auto &x : ve) {
        int fx = find(x.s), fy = find(x.e);
        if (fx != fy) {
            ++edge_num;
            maxx = max(maxx, x.w);
            fa[fx] = fy;
        }
    }
}

int main() {
    int n, m;
    vE ve;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int s, e, w;
        cin >> s >> e >> w;
        ve.push_back({s, e, w});
    }
    int edge_num = 0, maxx = 0;
    kruskal(ve, n, edge_num, maxx);
    cout << edge_num << ' ' << maxx;
    return 0;
}

这里引入一个概念，叫瓶颈生成树。

瓶颈生成树即在一个图的所有生成树中，最大的边权的值最小的生成树。

然后引入一个定理：最小生成树就是瓶颈生成树。

可用反证法证明：

假设最小生成树不是瓶颈生成树。

则可在最小生成树中权值最大的边，它的权值 $w$ 大于瓶颈生成树的最大权值。

既然大于的话，则存在一个更小的生成树，它的边中权值最大的一条，它的权值应该小于 $w$ 。这里就产生了矛盾，最小生成树本身就包含整个图当中权值最小的刚好连通所有结点的边，不可能存在生成树，它的所有边中权值最大的边的权值，小于最小生成树。

所以假设不成立，定理得证。

P2573 滑雪 - 洛谷 有向图的最小生成树

[P2573 SCOI2012] 滑雪 - 洛谷

轨道之间的交点可看成图的结点，轨道可看成图的边，能从一个交点滑到另一个交点需要有高度差在图中可表现为有方向。所以这个题可用有向图来进行建模。

题目要求的是用尽可能小的滑行距离即边权和，遍历最多的景点数。这个问题是求最小生成树。

但有向图因为边有方向，无法完全构建最小生成树使得每个点都在其中。但因为时间胶囊的设定，使得最小生成树也有可能包囊所有的结点，这里的有向图也能使用 prim 算法和 kruskal 算法求最小生成树。

确定求最小生成树时，就要考虑图的情况。若图分成几个互相不连通的子图，而起点又是固定的，不可能每个子图都生成最小生成树，或起点能到达的点有限。

所以需要先从主图中分离出一个子图，再从这个子图中分离出最小生成树。

分离子图即判断哪些点和起点连通，可通过 dfs 或 bfs 记录，这里使用 bfs 。然后这里选择使用 kruskal 算法求最小生成树。kruskal 算法求最小生成树需要对每条边进行排序，为了保证后续能包括更多的点，需要优先考虑边的尾部的高度，然后再考虑边的权值，即排序标准也要修改。

#include <bits/stdc++.h>
using namespace std;

using LL = long long;
using pll = pair<LL, LL>;
using vpll = vector<pair<LL, LL>>;
using vvpll = vector<vpll>;
using vl = vector<LL>;
using vb = vector<bool>;

vl hg;
LL n, m, cnt = 0, dist_sum = 0;
vvpll pct;
vb vis;

struct Edge {
    LL s;
    LL e;
    LL w;
    bool operator<(const Edge &aim) const {
        if (hg[e] != hg[aim.e])// 优先考虑有向边的尾结点
            return hg[e] > hg[aim.e];
        return w < aim.w;
    }
};
vector<Edge> ve;

void bfs(LL sx) {
    queue<LL> q;
    q.push(sx);
    vis[sx] = 1;//目的是求多少个点能被遍历，于是在入队时标记
    while (!q.empty()) {
        LL pt = q.front();
        q.pop();
        ++cnt;
        for (auto &x : pct[pt]) {
            int e = x.first, w = x.second;
            ve.push_back({pt, e, w});// 分离子图
            if (vis[e])
                continue;
            q.push(e);
            vis[e] = 1;
        }
    }
}

void kruskal() {
    vl fa(n + 1, 0);
    for (LL i = 1; i <= n; i++)
        fa[i] = i;
    auto find = [&fa](int x) {
        vl sk(1, x);
        while (x != fa[x]) {
            sk.push_back(fa[x]);
            x = fa[x];
        }
        for (auto &y : sk)
            fa[y] = x;
        return x;
    };
    
    sort(ve.begin(), ve.end());
    for (auto &x : ve) {
        int fx = find(x.s), fy = find(x.e);
        if (fx != fy) {
            dist_sum += x.w;
            fa[fx] = fy;
        }
    }
}

int main() {
    cin >> n >> m;
    hg.resize(n + 1, 0);
    vis.resize(n + 1, 0);
    pct.resize(n + 1);
    for (LL i = 1; i <= n; i++)
        cin >> hg[i];
    for (LL i = 1; i <= m; i++) {
        LL s, e, w;
        cin >> s >> e >> w;
        if (hg[s] >= hg[e])
            pct[s].push_back({e, w});
        if (hg[s] <= hg[e])// 两个结点的高度可能相同
            pct[e].push_back({s, w});
    }
    bfs(1);
    cout << cnt << ' ';
    kruskal();
    cout << dist_sum;
    return 0;
}

OJ参考

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

P1194 买礼物 - 洛谷

[P2330 SCOI2005] 繁忙的都市 - 洛谷

[P2573 SCOI2012] 滑雪 - 洛谷