最优灌溉

GitHub跳转原题关系图Canvas 关系图返回列表

按水渠费用升序用 Kruskal 选择不成环的边，得到连接全部麦田的最小生成树。

OJ: shumeng

题目 ID: CSP201412D

难度:普及-

标签:最小生成树并查集贪心

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 样例过程
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

把 nn 片麦田看作顶点，可修建的水渠看作带权边。求用最小总费用选出若干条边，使得所有顶点连通。

思路

先看小数据枚举边集的暴力：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:59
 */
// brute.cpp：小数据暴力解，枚举选择 n-1 条边并检查是否成树。
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u;
    int v;
    int cost;
};

int n, m;
vector<Edge> edges;
int choose_edge[25];
long long answer;

bool check_tree() {
    int parent[10];
    for (int i = 1; i <= n; i++) parent[i] = i;
    for (int i = 0; i < m; i++) {
        if (!choose_edge[i]) continue;
        int u = edges[i].u;
        int v = edges[i].v;
        while (parent[u] != u) u = parent[u];
        while (parent[v] != v) v = parent[v];
        if (u == v) return false;
        parent[u] = v;
    }
    int root = parent[1];
    while (parent[root] != root) root = parent[root];
    for (int i = 2; i <= n; i++) {
        int current = i;
        while (parent[current] != current) current = parent[current];
        if (current != root) return false;
    }
    return true;
}

void dfs(int pos, int selected, long long cost) {
    if (selected > n - 1 || selected + m - pos < n - 1) return;
    if (pos == m) {
        if (selected == n - 1 && check_tree()) answer = min(answer, cost);
        return;
    }
    choose_edge[pos] = 0;
    dfs(pos + 1, selected, cost);
    choose_edge[pos] = 1;
    dfs(pos + 1, selected + 1, cost + edges[pos].cost);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    edges.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].cost;
    }
    answer = (1LL << 60);
    dfs(0, 0, 0);
    cout << answer << '\n';
    return 0;
}

这正是最小生成树问题。将所有水渠按费用从小到大排序，依次考虑每条边：如果连接了两个不同连通块，就选择它；如果两端已经连通，选择会形成环，跳过。并查集维护当前连通块。

选出 n−1n-1 条边后，得到的费用就是答案。

样例过程

样例为 1-2(1)、2-3(4)、2-4(2)、3-4(3)，按费用排序后：

考虑的边 费用 两端连通块 决策
1-2 1 不同 选择，费用 1
2-4 2 不同 选择，费用 3
3-4 3 不同 选择，费用 6
2-3 4 已连通 跳过

三条边把 4 片麦田连通，最小费用为 1+2+3=61+2+3=6。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:59
 */
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u;
    int v;
    int cost;
};

int parent_node[1005];

int find_root(int x) {
    if (parent_node[x] == x) return x;
    return parent_node[x] = find_root(parent_node[x]);
}

bool compare_edge(const Edge &left, const Edge &right) {
    return left.cost < right.cost;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].cost;
    }

    sort(edges.begin(), edges.end(), compare_edge);
    for (int i = 1; i <= n; i++) parent_node[i] = i;

    long long answer = 0;
    int selected = 0;
    for (int i = 0; i < m && selected < n - 1; i++) {
        int root_u = find_root(edges[i].u);
        int root_v = find_root(edges[i].v);
        if (root_u == root_v) continue;
        parent_node[root_u] = root_v;
        answer += edges[i].cost;
        selected++;
    }

    cout << answer << '\n';
    return 0;
}

复杂度

排序占 O(mlog⁡m)O(m\log m)，每条边进行并查集操作，时间复杂度为 O(mlog⁡m)O(m\log m)；空间复杂度为 O(n+m)O(n+m)。

总结

Kruskal 的贪心依据是：当前最便宜的能连接两个连通块的边可以安全加入某棵最小生成树。并查集负责快速判断是否成环。