最小生成树

_RainCappuccino_ · 2024-12-29 19:38:37 · 算法·理论

摘自本人的图论一文

2. 最小生成树

基本问题：给定一个无向图，求该图边权和最小的生成树。

2.0 常用算法

2.0.1 Kruskal

基本思想：贪心

核心：将所有边按边权升序排序，对于边 (u, v, w)，u,v 此时没有联通，那么将此边加入最小生成树中，并连接 (u, v)。

优势：方便快捷，好些，稳定。

劣势：处理稠密图不够优秀。

时间复杂度: O(m \log m + m \alpha(n) )

2.0.2 Prim

基本思想：贪心

核心：找出没有与根相连的点中，距离已连接点最近的点加入树中。（有点类似 Dijkstra）

优势：稳定，处理稠密图比较快速。

劣势：不够好写。

时间复杂度:

• 朴素： O(n ^ 2 + m)
• 堆优化：O(m \log m)

2.1 在最小生成树上维护信息

具体为，题目所求信息可以通过在任意一个最小生成树上维护出来的情况。本质数据结构。

例题：

• P4180 [BJWC2010] 严格次小生成树

  给定一个无向图，求出严格次小生成树的边权和

  我们发现，严格次小生成树和最小生成树至多相差有一条边不同。

  证明： 如果有两条边不同，假设其边权为 w_1,w_2 和 w_3, w_4，w_1<w_3,w_2<w_3。

  那么我们只需要每次求出每条非树边可以替换的边中最大的和严格次大的边即可。这里求严格次大是因为要求严格次小。

  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  const int N = 1e5 + 10;
  const int M = 3e5 + 10;
  typedef long long ll;
  typedef pair<int, int> pi;
  //#define max(x, y) ((x) > (y) ? (x) : (y))
  //#define min(x, y) ((x) < (y) ? (x) : (y))
  int n, m;
  struct edge {
    int u, v, w;
    friend bool operator < (edge x, edge y) {
        return x.w < y.w;
    }
  }e[M];
  bool mark[M];
  int f[N], fa[N];
  int dep[N], son[N], dfn[N], top[N], siz[N], to[N];
  int tmp;
  vector<pi> g[N];
  int val[N];
  pi hb (int lmin ,int lmin2, int rmin, int rmin2) {
    int mi = max(lmin, rmin), mi2 = -1;
    if(lmin < rmin)   mi2 = lmin;
    else if(lmin > rmin) mi2 = rmin;
    mi2 = max(mi2, max(lmin2, rmin2));
    return make_pair(mi, mi2);
  }
  struct tree {
    int mi[N * 4], mi2[N * 4];
    #define mid (l + r >> 1)
    #define ls p << 1, l, mid
    #define rs (p << 1) | 1, mid + 1, r
    void build(int p, int l, int r) {
        if(l == r) mi[p] = val[to[l]], mi2[p] = -1;
        else {
            build(ls), build(rs);
            pi res = hb(mi[p << 1], mi2[p << 1], mi[(p << 1) | 1], mi2[(p << 1) | 1]);
            mi[p] = res.first, mi2[p] = res.second;
        }
    }
    pi getmin (int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) return make_pair(mi[p], mi2[p]);
        if(l > qr || r < ql) return make_pair(-1, -1);
        pi lson = getmin(ls, ql, qr), rson = getmin(rs, ql, qr);
        pi res = hb(lson.first, lson.second, rson.first, rson.second);
        return res;
    }
  }t;
  void dfs1 (int u, int fath) {
    dep[u] = dep[fath] + 1, siz[u] = 1, fa[u] = fath;
    for (auto e : g[u]) {
        int v = e.first, w = e.second;
        if(v == fath) continue;
        val[v] = w;
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
  }
  void dfs2 (int u, int tp) {
    top[u] = tp, dfn[u] = ++ tmp, to[tmp] = u;
    if(son[u]) dfs2(son[u], tp);
    for (auto e : g[u]) {
        int v = e.first, w = e.second;
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
  }
  pi getmin (int u, int v) {
    int first_u = u, first_v = v;
    pi res = {-1, -1};
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        pi tmp = t.getmin(1, 1, n, dfn[top[u]], dfn[u]);
        res = hb(res.first, res.second, tmp.first, tmp.second);
        u = fa[top[u]];
    }
    if(dep[u] < dep[v]) swap(u, v);
    pi tmp = t.getmin(1, 1, n, dfn[v] + 1, dfn[u]);
    res = hb(res.first, res.second, tmp.first, tmp.second);
    return res;
  }
  int find(int x) {
    if(f[x] == x) return f[x];
    return f[x] = find(f[x]);
  }
  
  signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    sort(e + 1, e + 1 + m);
    for (int i = 1; i <= n; i ++) f[i] = i;
    int now_res = 0;
    for (int i = 1; i <= m; i ++) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        int fu = find(u), fv = find(v);
        if(fu != fv) {
            f[fu] = fv;
            mark[i] = 1;
            now_res += w;
            g[u].push_back({v, w});
            g[v].push_back({u, w});
        }
    }
    val[1] = -1;
    dfs1 (1, -1);
    dfs2 (1, 1);
    t.build(1, 1, n);
    int ans = 1e18;
    for (int i = 1; i <= m; i ++) {
        if(!mark[i]) {
            int u = e[i].u, v = e[i].v, w = e[i].w;
            if(u == v) continue;
            pi res = getmin(u, v);
            if(res.first < w) {
                ans = min(now_res - res.first + w, ans);
            } else if(res.second < w && res.second != -1) {
                ans = min(now_res - res.second + w, ans);
            }
        }
    }
    cout << ans << endl;
    return 0;
  }

• CF827D Best Edge Weight

  给定一个点数为 n，边数为 m，权值不超过 10^9 的带权连通图，没有自环与重边。 现在要求对于每一条边求出，这条边的边权最大为多少时，它还能出现在所有可能的最小生成树上，如果对于任意边权都出现，则输出 -1。 ( 2 \le n \le 2 \times 10^5, n - 1 \le m \le 2 \times 10^5)

  分类讨论，现在求出的任意一个最小生成树为 G\{V,E\}。

  对于 e \in E，即树边，有两种情况：

  • 无论何值都必定在最小生成树上，不难发现，一定是割边，或者用非另一种情况去判断。
  • 否则，最大值为 (\min\limits _{e'(u,v) \notin E,e \in u \leftrightsquigarrow v}w_{e'}) - 1，原因：在这棵 MST 的基础上，删去一条边，再加上一条边，一定只能替换新加边 (u, v) 的两个顶点在原树上 u \leftrightsquigarrow v 的唯一路径上的边，不然不能满足树的联通性。

  对于 e(u,v) \notin E，即非树边，答案只能为 (\max\limits _{e' \in E,e' \in u \leftrightsquigarrow v}w_{e'}) - 1。原因同树边的第二种情况。

  对于树边的情况 2，转化一下，设对于树边 (x, y) 最后的答案是 f_i，就是对于所有非树边 (u, v)，对 u\leftrightsquigarrow v 上的边，f_i \gets \min(f_i, w_{(u,v)})，直接暴力树剖是 n \log^2 n 的，我们剋癌的 NKOJ 肯定跑不过去。发现这个操作是先修改完毕再查询，可以考虑倍增处理再下放，如果没有被任意一个非树边覆盖过，那么就是情况 1。

  对于树边，就是简单的树上倍增求 \max 即可。

  #include <bits/stdc++.h>
  using namespace std;
  #define endl '\n'
  const int N = 2e5 + 10;
  const int M = 2e5 + 10;
  const int inf = 0x3f3f3f3f;
  typedef long long ll;
  typedef pair<int, int> pi;
  int n, m;
  struct edge {
  int u, v, w, id;
  bool operator < (edge x) const {
      return w < x.w;
  }
  } e[M];
  vector<edge> g[N], g2[N];
  struct dsu {
  int f[N];
  void init () {
      for (int i = 1; i <= n; i ++) f[i] = i;
  }
  int find (int x) {
      return f[x] = (f[x] == x ? x : find(f[x]));
  }
  } d;
  int son[N], dep[N], fath[N], dfn[N], top[N], siz[N], tmp, to[N], val[N];
  int bel[M];
  int fa[N][40], k;
  void dfs1 (int u, int _fa) {
  siz[u] = 1, fath[u] = _fa, dep[u] = dep[_fa] + 1;
  fa[u][0] = _fa;
  for (int i = 1; ; i ++) {
      fa[u][i] = fa[fa[u][i - 1]][i - 1];
      if (!fa[u][i]) {
          k = max(k, i - 1);
          break;
      }
  }
  for (auto e : g[u]) {
      int v = e.v;
      if (v == _fa) continue;
      val[v] = e.w, bel[e.id] = v;
      dfs1 (v, u);
      if (siz[v] > siz[son[u]]) son[u] = v;
      siz[u] += siz[v];
  }
  }
  int mi[N][40];
  void modify (int u, int v, int val) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = k; i >= 0; i --) {
      if (dep[fa[u][i]] >= dep[v]) {
          mi[u][i] = val;
          u = fa[u][i];
      }
  }
  if (u == v) return;
  for (int i = k; i >= 0; i --) {
      if (fa[u][i] != fa[v][i]) {
          mi[u][i] = mi[v][i] = val;
          u = fa[u][i], v = fa[v][i];
      }
  }
  mi[u][0] = mi[v][0] = val;
  }
  void pushdown () {
  for (int i = k; i >= 1; i --) {
      for (int j = 1; j <= n; j ++) {
          if (!mi[j][i]) continue;
          mi[j][i - 1] = min(mi[j][i - 1], mi[j][i]);
          mi[fa[j][i - 1]][i - 1] = min(mi[fa[j][i - 1]][i - 1], mi[j][i]);
      }
  }
  }
  void dfs2 (int u, int tp) {
  top[u] = tp, dfn[u] = ++ tmp, to[tmp] = u;
  if (son[u]) dfs2(son[u], tp);
  for (auto e : g[u]) {
      if (e.v == fath[u] || e.v == son[u]) continue;
      dfs2 (e.v, e.v);
  }
  }
  int log_2[N];
  struct tree {
  int ma[N][40];
  void build() {
      for (int i = 1; i <= n; i ++) ma[i][0] = val[to[i]];
      for (int k = 1; (1 << k) <= n; k ++) {
          for (int i = 1; i + (1 << k) - 1 <= n; i ++) {
              ma[i][k] = max(ma[i][k - 1], ma[i + (1 << k - 1)][k - 1]);
          }
      }
  }
  int getmax (int ql, int qr) {
      int len = log_2[qr - ql + 1];
      return max (ma[ql][len], ma[qr - (1 << len) + 1][len]);
  }
  } t;
  int getmax (int u, int v) {
  int res = 0;
  while (top[u] != top[v]) {
      if (dep[top[u]] < dep[top[v]]) swap(u, v);
      res = max(t.getmax(dfn[top[u]], dfn[u]), res);
      u = fath[top[u]];
  }
  if (dep[u] < dep[v]) swap(u, v);
  if (u == v) return res;
  res = max(res, t.getmax(dfn[v] + 1, dfn[u]));
  return res;
  }
  int befu[M], befv[M];
  bool mark[M], mk[M];
  #ifdef ONLINE_JUDGE
  char buf[1 << 23] , * p1 = buf , * p2 = buf , obuf[1 << 23] , * O = obuf;
  #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
  #endif
  inline int read() {
  int x = 0 , f = 1;char ch = getchar();
  while (!isdigit(ch)) { if (ch == '-') f = -1;ch = getchar(); }
  while (isdigit(ch)) x = x * 10 + (ch ^ 48) , ch = getchar();
  return x * f;
  }
  signed main() {
  //    freopen("in.txt", "r", stdin);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  n = read(), m = read();
  for (int i = 1; i <= n; i ++) d.f[i] = i, log_2[i] = log2(i);
  for (int i = 1; i <= m; i ++) e[i].u = read(), e[i].v = read(), e[i].w = read(), e[i].id = i, befu[i] = e[i].u, befv[i] = e[i].v;
  sort (e + 1, e + 1 + m);
  for (int i = 1; i <= m; i ++) {
      int u = e[i].u, v = e[i].v;
      if (d.find(u) != d.find(v)) {
          d.f[d.find(u)] = d.find(v);
          mk[e[i].id] = 1;
          g[u].push_back({u, v, e[i].w, e[i].id});
          g[v].push_back({v, u, e[i].w, e[i].id});
      }
      g2[u].push_back({u, v, e[i].w, e[i].id});
      g2[v].push_back({v, u, e[i].w, e[i].id});
  }
  dfs1 (1, 0);
  dfs2 (1, 1);
  for (int i = 1; i <= n; i ++)
      for (int j = 0; j <= k; j ++) mi[i][j] = inf;
  t.build();
  for (int i = m; i >= 1; i --) {
      if (!mk[e[i].id]) modify(e[i].u, e[i].v, e[i].w);
  }
  pushdown();
  for (int id = 1; id <= m; id ++) {
      if (mk[id]) {
          int u = bel[id];
          int v = mi[u][0];
          if (v == inf) cout << -1 << ' ';
          else cout << v - 1 << ' ';
      } else {
          cout << getmax(befu[id], befv[id]) - 1 << ' ';
      }
  }
  return 0;
  }

2.2 最小/大瓶颈树

当要求生成树两点之间路径上边权的最大值/最小值尽肯能小/大，此时，最小/最大生成树就是最优的解。原因：最小生成树上的边一定是原图中边权尽可能小的边。

例题：

• [NOIP2013 提高组] 货车运输

  给定一个 n 个点 m 条边的图，q 次询问，每次询问两个点 u,v，请求出 u,v 的所有路径中，路径上最大边的最小值。

  板题，求了最大生成树后用树上倍增求两点之间路径上边权的最大值。

  #include <bits/stdc++.h>
  using namespace std;
  
  const int N = 1e5 + 10;
  
  int n, m;
  struct edge {
    int u, v, w;
    friend bool operator < (edge x, edge y) {
        return x.w > y.w;
    }
  }e[N];
  int f[N];
  int find (int x) {
    if(f[x] != x) f[x] = find(f[x]);
    return f[x];
  }
  vector<pair<int, int> > G[N];
  
  bool vis[N];
  int maxn[N][30], fa[N][30], k;
  int dep[N];
  void dfs (int u, int fath) {
    dep[u] = dep[fath] + 1;
    fa[u][0] = fath, vis[u] = 1;
    for (int i = 1; ; i ++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
        maxn[u][i] = min(maxn[u][i - 1], maxn[fa[u][i - 1]][i - 1]);
        if(!fa[u][i]) {
            k = max(k, i - 1);
            break;
        }
    }
    for (auto eg : G[u]) {
        int v = eg.first, w = eg.second;
        if(v != fath) {
            maxn[v][0] = w;
            dfs(v, u);
        }
    }
  }
  int getmax (int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    int mau = 0x3f3f3f3f;
    for (int i = k; i >= 0; i --) {
        if(dep[fa[u][i]] >= dep[v]) {
            mau = min(mau, maxn[u][i]);
            u = fa[u][i];
        }
    }
    if(u == v) return mau;
    for (int i = k; i >= 0; i --) {
        if(fa[u][i] != fa[v][i]) {
            mau = min(mau, min(maxn[u][i], maxn[v][i]));
            u = fa[u][i], v = fa[v][i];
        }
    }
    mau = min(mau, min(maxn[u][0], maxn[v][0]));
    return mau;
  }
  
  signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) f[i] = i;
    for (int i = 1; i <= m; i ++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    sort(e + 1, e + 1 + m);
    for (int i = 1; i <= m; i ++ ) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        if(find(u) != find(v)) {
            f[find(v)] = find(u);
            G[u].push_back({v, w}), G[v].push_back({u, w});
        }
    }
    for (int i = 1; i <= n; i ++) {
        if(!vis[i]) dfs(i, 0);
    }
    int q;
    cin >> q;
    while(q --) {
        int u, v;
        cin >> u >> v;
        if(find(u) != find(v)) cout << -1 << endl;
        else {
            cout << getmax(u, v) << endl;
        }
    }
    return 0;
  }

• JOI 2014 T5 水筒 <span id="jump">back</span>

  给定一个 h \times w 的网格图，其中有 p 个建筑物，每次询问两个建筑物 u,v，请求出 u,v 的所有路径中，路径上最小边的最大值。

  具体做法同上，但是建边需要优化。用多源 bfs 求出每个点距离最近的建筑物，将其归属于该建筑，会形成 p 个区域，我们发现，两个建筑物之间只考虑两个相邻的不同所属的点比考虑跨越多个区域要更优。于是，边的量级优化到了 O(hw)。

  // Main
  namespace bfs {
  int bel[N][N];
  int dis[N][N];
  int dx[] = {0, 0, 1, -1};
  int dy[] = {1, -1, 0, 0};
  queue<pi> q;
  #define x first
  #define y second
    void bfs () {
        memset(dis, 0x3f, sizeof dis);
        for (int i = 1; i <= p; i ++) q.push({sx[i], sy[i]}), bel[sx[i]][sy[i]] = i, dis[sx[i]][sy[i]] = 0;
        while (!q.empty()) {
            int x = q.front().x, y = q.front().y;
            q.pop();
            for (int i = 0; i < 4; i ++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (!nx || !ny || nx > h || ny > w || mp[nx][ny] == '#' || bel[nx][ny] == bel[x][y]) continue;
                if (dis[x][y] + 1 < dis[nx][ny]) {
                    dis[nx][ny] = dis[x][y] + 1;
                    bel[nx][ny] = bel[x][y];
                    q.push({nx, ny});
                } else if (bel[x][y] != bel[nx][ny]) {
                    int u = bel[x][y], v = bel[nx][ny];
                    g[u].push_back({v, dis[nx][ny] + dis[x][y]});
                    g[v].push_back({u, dis[nx][ny] + dis[x][y]});
                }
            }
        }
    }
  };

2.3 Kruskal 优化建图

根据 Kruskal 的原理，有时候我们发现有一些边是冗余的边（比如一定可以证明不比另一些边优的），可以不考虑这些边来优化时间复杂度。

例题：

• P8207 [THUPC2022 初赛] 最小公倍树

  给定一个完全图，点的编号为 L \sim R(R - L \le 10^5, 1 \le L \le R\le 10^6)，任意一条边 (u, v) 的权值为 \text{lcm}(u,v) 求最小生成树。

  考虑 \text{lcm}(u,v) 的形式：\frac{uv}{\gcd(u,v)}。发现，当两个数的公共因子尽可能大的时候，这条边权值越小。

  所以不妨尝试枚举这里的因子 x，此时，设 \in [L, R] 的 x 的倍数为 ax, ax+x, ax+2\times x, \dots,ax + k \times x 。贪心地想，从 ax 连向其他所有点一定更优。原因：

  • 设连接的两点为 (a + d)x, (a + e)x，如果 \gcd(a + d, a + e) = 1，那么 (a + e) \times (a + d) \ge a \times(a + d)。一定不比连接 (ax, (a + d) x) 优。
  • 若不互质，那么在之后枚举到因子 x \times (a + d, a + e) 时也会考虑到，所以在此时枚举时冗余的。

  枚举的复杂度时调和级数，所以最后时间复杂度为 O((R -L) \log^2(R - L))。

  #include <bits/stdc++.h>
  using namespace std;
  const int N = 1e6 + 10;
  #define int long long
  int l, r, tot;
  struct edge {
  int u, v, w;
  friend bool operator < (edge x, edge y) {
      return x.w < y.w;
  }
  }e[N * 2];
  int f[N];
  int lcm (int x, int y) {return x * y / __gcd(x, y);}
  int find(int x) {
  return f[x] = (f[x] == x) ? x : find(f[x]);
  }
  
  signed main() {
  ios::sync_with_stdio(0);
  cin >> l >> r;
  for (int i = l; i <= r; i ++) f[i] = i;
  for (int i = 2; i <= r; i ++) {
      int first = ((l - 1) / i + 1) * i;
      for (int j = first + i; j <= r; j += i) {
          e[++ tot] = edge{first, j, lcm(first, j)};
      }
      if(i >= l) e[++ tot] = edge{first, l, lcm(first, l)};
  }
  sort(e + 1, e + 1 + tot);
  int w = 0, cnt = 0;
  for (int i = 1; i <= tot; i ++) {
      if(find(e[i].u) != find(e[i].v)) {
          cnt ++;
          f[find(e[i].u)] = find(e[i].v);
          w += e[i].w;
      }
  }
  cout << w << endl;
  return 0;
  }

• JOI 2014 T5 水筒