• 前言
• 题目大意
• 思路
  • prim
    • 什么时候用prim
      • 稀疏图
      • 稠密图
• 代码
• 总结

前言

介绍本题的prim做法。但其实用哪种算法都行。

题目大意

给出一个图的邻接矩阵，求这张图的最小生成树的边权总和。

$1\leq n\leq 100$

思路

prim是一个点找边的算法。

prim

prim是一种最小生成树做法，朴素的做法为 $\mathcal{O}(n^2)$。由于老师只讲了 $\mathcal{O}(n^2)$ 的做法，所以这里就介绍它。

要遍历每一个点，通常从一开始，假设现在在 $u$。之后 $ans+val[u]$ 也就是选择了这个点，加上这个点的值。同时将这个点设成虚的，就是之后不再遍历。然后每一个出边的值为这个点与 $v$ 的边权和原本的 $val[v]$ 的最小值。前提是 $v$ 还是实心的。这也有点类似一个我为人人的思路。

什么时候用prim

kruskal时间复杂度是 $\mathcal{O}(E\log{E})$ 左右。
prim的时间复杂度是 $\mathcal{O}(V^2)$。

稀疏图

V和E在一个数量级
kruskal时间复杂度是 $\mathcal{O}(V\log{V})$ 左右。
prim的时间复杂度是 $\mathcal{O}(V^2)$。
前者更好

稠密图

E和V^2在一个数量级
kruskal时间复杂度是 $\mathcal{O}(V^2\log{V^2})$ 左右。
prim的时间复杂度是 $\mathcal{O}(V^2)$
前者比后者多一个 $\log$，后者更优。

总之各有各的好处。

代码

#include <iostream>

using namespace std;
typedef long long ll;
const ll MAXN = 105;
const ll INF = 0x3f3f3f3f3f3f;
ll n, val[MAXN], adj[MAXN][MAXN];
bool vis[MAXN];

ll prim() {
    ll num = 0;
    for (int i = 0; i <= n; ++i) {
        val[i] = INF;//首先先把所有的值设为INF，也代表还没有遍历过
        vis[i] = false;//所有点是实心的。
    }
    val[1] = 0;//从1开始，那么1的价值肯定是0，因为没有任何的边权经过。
    for (int i = 1; i <= n; ++i) {
        ll chose = 0;//选哪个
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && val[j] < val[chose]) {
                chose = j;//选择一个没有遍历过且权值最小。一开始由于设成0了就一定选1
            }
        }
        vis[chose] = true;//设为虚的
        num += val[chose];//加上这个选择
        for (int j = 1; j <= n; ++j) {
            if (vis[j] == 0 && val[j] > adj[chose][j]) {
                val[j] = adj[chose][j];//实心的点用“我为人人”
            }
        }
    }
    return num;
}

int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%lld", &adj[i][j]);
        }
    }
    printf("%lld\n", prim());
    return 0;
}

复制代码

总结

学习了prim的 $\mathcal{O}(n^2)$ 做法。