新的开始

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 985 字

虚拟源点建发电站，Prim求最小生成树

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1488
// 题意：n 口矿井，在第 i 口建发电站花 v_i，在 i、j 间架电网花 p_ij，求让所有矿井都通电的最小总花费。
// 思路：新增一个 0 号虚拟点，0 到 i 连一条权为 v_i 的边表示建发电站，然后在这 n+1 个点上跑 Prim 求最小生成树。
// 复杂度：O(n^2) 时间 / O(n^2) 空间
// 易错点：建发电站是「把该点接入电网」的一次性代价，必须建成虚拟点的边，不能简单地在最小花费的矿井上建一座。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 305;
const long long INF = (1LL << 60);
long long p[MAXN][MAXN];
long long d[MAXN];
bool vis[MAXN];
int main(){
    int n;
    if(!(cin >> n)) return 0;
    for(int i = 1; i <= n; i++) cin >> d[i];
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) cin >> p[i][j];
    }
    long long ans = 0;
    for(int it = 1; it <= n; it++){
        int u = 0;
        for(int i = 1; i <= n; i++){
            if(!vis[i] && (u == 0 || d[i] < d[u])) u = i;
        }
        vis[u] = true;
        ans += d[u];
        for(int v = 1; v <= n; v++){
            if(!vis[v] && p[u][v] < d[v]) d[v] = p[u][v];
        }
    }
    cout << ans << '\n';
    return 0;
}

新的开始

正文

一本通·提高篇的其它内容