最小生成树prim算法

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int N = 55, inf = 0x3f3f3f3f;

int g[N][N], dist[N], n;

bool st[N];

int prim()

{

    memset(dist, 0x3f, sizeof dist);

    int res = 0;

    for (int i = 0; i < n; i++)

    {

        int t = -1;

        for (int j = 1; j <= n; j++)

            if (!st[j] && (t == -1 || dist[t] > dist[j]))

                t = j;

        if (i&& dist[t] == inf)

            return inf;

        if (i)

            res += dist[t];

        for (int j = 1; j <= n; j++)

            dist[j] = min(dist[j], g[t][j]);

        st[t] = true;

    }

    return res;

}

int main()

{

    scanf("%d", &n);

    for (int i = 1; i <= n; i++)

    {

        for (int j = 1; j <= n; j++)

        {

            scanf("%d", &g[i][j]);

            if (i!=j &&g[i][j] == 0)

                g[i][j] = inf;

        }

    }

    int t = prim();

    printf("%d\n", t);

    return 0;

}