跳转至

最小生成树⚓︎

最小生成树（\text{Minimum Spanning Tree}, \text{MST}）是指在一个连通加权无向图中，选取一部分边，使得所有节点都连通且边的权重之和最小的生成树。常用的算法有 \text{Kruskal} 算法和 \text{Prim} 算法。

Kruskal算法⚓︎

\text{Kruskal} 算法的基本思想是将所有边按权重从小到大排序，然后依次选择边，若选择该边不会形成环，则将其加入生成树中，直到生成树包含所有节点为止。通常使用并查集（\text{Union-Find}）来检测环的形成。

【模板】最小生成树

给定一个包含 n 个节点和 m 条边的无向图，求该图的最小生成树的权值和。如果图不连通，则输出 "orz"。

C++
#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

struct Edge {
  int u, v, weight;

  bool operator<(const Edge &other) const { return weight < other.weight; }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.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].weight; }

  // 并查集
  vector<int> root(n + 1);
  iota(root.begin(), root.end(), 0);

  function<int(int)> find = [&](int x) {
    if (root[x] != x) { root[x] = find(root[x]); }
    return root[x];
  };

  sort(edges.begin(), edges.end());

  int mst_weight  = 0;
  int edges_count = 0;

  for (const auto &edge : edges) {
    int root_u = find(edge.u);
    int root_v = find(edge.v);
    if (root_u != root_v) {
      mst_weight += edge.weight;
      edges_count++;
      root[root_u] = root_v;
      if (edges_count == n - 1) { break; }  // early stop
    }
  }

  if (edges_count == n - 1) {
    cout << mst_weight << "\n";
  } else {
    cout << "orz\n";
  }

  return 0;
}

Prim算法⚓︎

\text{Prim} 算法的基本思想是从一个节点开始，逐步扩展生成树，每次选择一条连接生成树和非生成树的边中权重最小的边，将其加入生成树，直到所有节点都包含在生成树中。通常使用优先队列（\text{Priority Queue}）来高效地选择最小权重边。

【模板】最小生成树

C++
#include <algorithm>
#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

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

  int n, m;
  cin >> n >> m;

  using PII = pair<int, int>;
  vector<vector<PII>> graph(n + 1);

  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    graph[u].emplace_back(v, w);
    graph[v].emplace_back(u, w);
  }

  vector<int> min_edge(n + 1, INT_MAX);  // 记录每个节点到生成树的最小边权 (1)
  vector<bool> in_mst(n + 1, false);
  priority_queue<PII, vector<PII>, greater<>> pq;  // {weight, vertex}

  min_edge[1] = 0;
  pq.emplace(0, 1);

  int mst_weight = 0;

  while (!pq.empty()) {
    auto [weight, u] = pq.top();
    pq.pop();

    if (in_mst[u]) { continue; }
    in_mst[u]   = true;
    mst_weight += weight;

    for (const auto &[v, w] : graph[u]) {
      if (!in_mst[v] && w < min_edge[v]) {  // 找到更小的边
        min_edge[v] = w;
        pq.emplace(w, v);
      }
    }
  }

  if (all_of(in_mst.begin() + 1, in_mst.end(), [](bool x) { return x; })) {
    cout << mst_weight << "\n";
  } else {
    cout << "orz\n";
  }

  return 0;
}

  1. 避免重复插入同一节点到优先队列中，确保每个节点只会被加入生成树一次。也可以省略，常数时间会稍微高一些。

Kruskal重构树⚓︎

\text{Kruskal} 重构树是一种基于 \text{Kruskal} 算法构建的树形结构，用于表示最小生成树的合并过程。每次合并两个连通分量时，创建一个新的节点表示该合并操作，并将两个被合并的节点作为其子节点，节点权重为边的权重。这样，最终得到的树的根节点表示整个图的最小生成树。

对于无向图，原图中两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = \text{Kruskal} 重构树上两点之间的 \text{LCA} 的权值。

对于有 n 个节点的无向图，\text{Kruskal} 重构树最多有 2n-1 个节点，其中前 n 个节点对应原图的节点，后 n-1 个节点对应合并操作。

利用 \text{Kruskal} 重构树，可以高效地处理一些与最小生成树相关的查询问题，例如查询两个节点在最小生成树中的最大边权等。

星际导航

给定一个包含 n 个节点和 m 条边的无向图，询问 q 次，每次询问两个节点 u 和 v，求在最小生成树中连接 u 和 v 的路径上权重最大的边。如果 u 和 v 不连通，则输出 "impossible"。

C++
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t n, m;
  cin >> n >> m;
  using TIII = tuple<int64_t, int64_t, int64_t>;
  vector<int64_t> node(2 * n);  // 最多有 n-1 个新节点, 总节点数不超过 2n-1
  vector<vector<int64_t>> tree(2 * n);
  vector<TIII> edges(m);
  for (int64_t i = 0; i < m; ++i) {
    int64_t u, v, w;
    cin >> u >> v >> w;
    edges[i] = {w, u, v};
  }

  vector<int64_t> root(2 * n);
  iota(root.begin(), root.end(), 0);
  auto find = [&](int64_t x) {
    while (root[x] != x) {
      root[x] = root[root[x]];
      x       = root[x];
    }
    return x;
  };

  // Kruskal重构
  sort(edges.begin(), edges.end());
  int64_t idx = n;
  for (const auto &[w, u, v] : edges) {
    int64_t ru = find(u);
    int64_t rv = find(v);
    if (ru != rv) {
      root[ru] = root[rv] = ++idx;
      node[idx]           = w;
      tree[idx].emplace_back(ru);
      tree[idx].emplace_back(rv);
    }
  }

  // LCA预处理
  vector<int64_t> depth(idx + 1, 0);
  int64_t M = 32 - __builtin_clz(idx + 1);
  vector<vector<int64_t>> st(idx + 1, vector<int64_t>(M + 1, -1));
  auto dfs = [&](auto &&self, int64_t u, int64_t p) -> void {
    st[u][0] = p;
    for (int64_t i = 1; i <= M; ++i) {
      if (st[u][i - 1] != -1) { st[u][i] = st[st[u][i - 1]][i - 1]; }
    }
    for (const auto &v : tree[u]) {
      if (v != p) {
        depth[v] = depth[u] + 1;
        self(self, v, u);
      }
    }
  };
  for (int64_t i = 1; i <= idx; ++i) {      // 图可能不连通
    if (root[i] == i) { dfs(dfs, i, -1); }  // 从每个连通块的根节点开始dfs
  }

  auto get_kth_ancestor = [&](int node, int k) -> int {
    for (; (k != 0) && (node != -1); k &= k - 1) { node = st[node][__builtin_ctz(k)]; }
    return node;
  };

  auto get_lca = [&](int x, int y) -> int {
    if (depth[x] > depth[y]) { swap(x, y); }
    y = get_kth_ancestor(y, depth[y] - depth[x]);
    if (y == x) { return x; }
    for (int i = M - 1; i >= 0; --i) {
      int px = st[x][i];
      int py = st[y][i];
      if (px != py) {
        x = px;
        y = py;
      }
    }
    return st[x][0];
  };

  int64_t q;
  cin >> q;
  for (int64_t i = 0; i < q; ++i) {
    int64_t x, y;
    cin >> x >> y;
    if (find(x) != find(y)) {
      cout << "impossible\n";
    } else {
      int64_t lca = get_lca(x, y);
      cout << node[lca] << "\n";
    }
  }

  return 0;
}
最小瓶颈路（加强版）

给定一个 n 个点 m 条边的无向连通图，编号为 1 到 n，没有自环，可能有重边，每一条边有一个正权值 w。

给出 q 个询问，每次给出两个不同的点 u 和 v，求一条从 u 到 v 的路径上边权的最大值最小是多少。

数据量 n 和 q 不同阶

C++
#include <algorithm>
#include <iostream>
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

int A, B, C, P;

inline int rnd() { return A = (A * B + C) % P; };

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m;
  cin >> n >> m;
  using TIII = tuple<int, int, int>;
  vector<int> node(2 * n);  // 最多有 n-1 个新节点
  vector<vector<int>> tree(2 * n);
  vector<TIII> edges(m);
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    edges[i] = {w, u, v};
  }

  vector<int> root(2 * n);
  iota(root.begin(), root.end(), 0);
  auto find = [&](int x) {
    while (root[x] != x) {
      root[x] = root[root[x]];
      x       = root[x];
    }
    return x;
  };

  // Kruskal重构
  sort(edges.begin(), edges.end());
  int idx = n, edge_count = 0;
  for (const auto &[w, u, v] : edges) {
    int ru = find(u);
    int rv = find(v);
    if (ru != rv) {
      ++idx;
      root[ru] = root[rv] = idx;
      node[idx]           = w;
      tree[idx].emplace_back(ru);
      tree[idx].emplace_back(rv);
      ++edge_count;
    }
    if (edge_count == n - 1) { break; }
  }

  int q;
  cin >> q >> A >> B >> C >> P;
  // Tarjan离线LCA
  vector<vector<pair<int, int>>> query(idx + 1);
  for (int i = 0; i < q; ++i) {
    int x = rnd() % n + 1;
    int y = rnd() % n + 1;
    query[x].emplace_back(y, i);
    query[y].emplace_back(x, i);
  }
  vector<bool> visited(2 * n);
  vector<int> answer(q);
  iota(root.begin(), root.end(), 0);
  auto dfs = [&](auto &&self, int x, int from) -> void {
    visited[x] = true;
    for (int y : tree[x]) {
      if (y != from) {
        self(self, y, x);
        root[y] = x;  // 合并 y 和 x
      }
    }
    for (auto [y, idx] : query[x]) {              // 处理所有和 x 有关的查询
      if (visited[y]) { answer[idx] = find(y); }  // y 已经访问过, 说明 LCA 已经确定
    }
  };
  dfs(dfs, idx, -1); // 从根节点开始DFS

  const int mod = 1e9 + 7;
  int ans       = 0;
  for (int lca : answer) { ans = (ans + node[lca]) % mod; }
  cout << ans << "\n";

  return 0;
}

评论