【ybtoj 高效进阶 3.2】【最小生成树】 新的开始

题目

---

解题思路

将建设发电站的费用看作是连向超级点的边权
从超级点开始跑一边prim即可

---

代码

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n, x, tot , mi = 1, f[320], p[320], a[320][320];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d",&a[1][i+1]);  //1点是超级点，把矿井编号向后一位
    }
    memset(f, 0x7f, sizeof(f));
    memset(p, 0, sizeof(p));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) scanf("%d", &a[i+1][j+1]);
        a[i][i] = f[0];  //自己和自己没有路
    }
    f[1] = 0;
    for (int j = 1; j <= n+1; j++) {
        int k = 0;
        for (int i = 1; i <= n+1; i++)
            if (!p[i] && f[i] < f[k])
                k = i;
        p[k] = 1;
        tot += f[k];
        for (int i = 1; i <= n+1; i++)
            if (a[k][i] < f[i])
                f[i] = a[k][i];
    }  //prim
    printf("%d", tot);
    return 0;
}