Author: lllyouo
Date: 20250224
tag: 最小生成树、虚拟源点
link: https://www.acwing.com/problem/content/1148/

问题描述

link

分析

设立虚拟源点，对于直接建立发电站的费用，建立虚拟源点到该点的一条边，权值即为建立发电站的费用，之后做最小生成树算法。

参考代码

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

const int N = 310;
struct Edge {
    int u, v, w;

    bool operator< (const Edge& x) {
        return w < x.w;
    }
};

vector<Edge> e;
int n, p[N], ans;

int find(int x) {
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int t; cin >> t;
        e.push_back({0, i, t});
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int t; cin >> t;
            if (i != j) e.push_back({i, j, t});
        }
    }
    
    sort(e.begin(), e.end());
    for (int i = 1; i <= n; i++) p[i] = i;

    for (int i = 0; i < e.size(); i++) {
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if (fu != fv) {
            p[fu] = fv;
            ans += e[i].w;
        }
    }
    cout << ans << endl;

    return 0;
}