Author: lllyouo
Date: 20250225
tag: 最小生成树
link: https://www.acwing.com/problem/content/349/

问题描述

给定一张 $N(N\le 30)$ 个点 $M$ 条边的无向图，求出无向图的一颗最小生成树，满足 $1$ 号点的度数不超过给定的整数 $S$。

分析

首先建立最小生成树，记最小生成树权值之和为 $res$，$1$ 号点的度数为 $deg$，之后考虑每次删除最小生成树中与 $1$ 号点相连的一条权值最大的边 $(x,y,z)$，此时会出现一个连通块 $A$，且 $res=res-z$，考虑 $A$ 中的点与除 $1$ 号点之外其他顶点相连的一条权值最小的边 $(u,v,w)$，连接该边之后 $res=res+w$，对每次计算的 $res$ 取 $min$。

参考代码

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

const int N = 35;
int n, m, s, res, deg, a[N][N]；
// 记录最小生成树中的边
int conn[N];
// 存最小生成树
int tr[N][N];
int dist[N], vis[N];

void read() {
    map<string, int> h;
    cin >> m;
    h["Park"] = 1; n = 1;
    memset(a, 0x3f, sizeof a);
    for (int i = 0; i < m; i++) {
        string x, y;
        int l;
        cin >> x >> y >> l;
        if (!h[x]) h[x] = ++n;
        if (!h[y]) h[y] = ++n;
        int hx = h[x], hy = h[y];
        a[hx][hy] = min(a[hx][hy], l);
        a[hy][hx] = min(a[hy][hx], l);
    }
    cin >> s;
}

void prime() {
    memset(dist, 0x3f, sizeof dist);
    memset(vis, 0, sizeof vis);
    dist[1] = 0;

    for (int i = 1; i < n; i++) {
        int k = -1;
        for (int j = 1; j <= n; j++) { // 找出距离集合最近的点 
            if (!vis[j] && (k == - 1 || dist[j] < dist[k])) k = j;
        }
        vis[k] = 1;
        
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && dist[j] > a[k][j]) {
                dist[j] = a[k][j], conn[j] = k;
            }
        }
    }
    
    memset(tr, 0x3f, sizeof tr);
    for (int i = 2; i <= n; i++) {
        res += dist[i];
        if (conn[i] == 1) deg++;
        tr[conn[i]][i] = tr[i][conn[i]] = dist[i];
    }
}

void dfs(int x) {
    vis[x] = true;
    for (int y = 1; y <= n; y++) {
        if (tr[x][y] != 0x3f3f3f3f && !vis[y]) dfs(y);
    }
}

void solve() {
	// (1, mini, c1) 记录删除的边
	// (minx, miny, c2) 记录添加的边
	// minv 记录两条边的权值之差 c2 - c1
    int minv = 1 << 30, mini, minx, miny;
    for (int i = 2; i <= n; i++) { // 枚举 1 的所有出边 (1, i)
        if (tr[1][i] == 0x3f3f3f3f) continue;
	    
        // 标记删除 (1, i) 之后产生的连通块
        memset(vis, 0, sizeof vis);
        vis[1] = true;
        dfs(i);
        
        // 枚举连接两个连通块的权值最小的边 (u, v, w)
        int u = -1, v = -1, minw = 1 << 30;
        for (int x = 2; x <= n; x++) {
            if (vis[x]) {
                for (int y = 2; y <= n; y++) {
                    if (!vis[y]) {
                        if (a[x][y] < minw) {
                            minw = a[x][y];
                            u = x;
                            v = y;
                        }
                    }
                }
            }
        }
        
        if (minw < 0x3f3f3f3f && minw - tr[1][i] < minv) {
            minv = minw - tr[1][i];
            mini = i, minx = u, miny = v;
        } 
    }
    
    res += minv;
    tr[1][mini] = tr[mini][1] = 0x3f3f3f3f;
    tr[minx][miny] = tr[miny][minx] = a[minx][miny];
}

int main() {
    read();
    prime();
    while (deg > s) {
        solve();
        deg--;
    }
    cout << "Total miles driven: " << res << endl;
        
    return 0;
}