prim邻接表做法

(prim) $O(n^2)$

C++ 代码

// 这个算法和dijkstra算法很像，只不过把距离最初点的距离变成了距离整个点集合的距离
#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, M = 200010, md = 0x3f3f3f3f;

int e[M], ne[M], h[N], idx = 0; // 邻接表
int w[N][N], dist[N]; // 边权重数组， 点距离集合的数组
int sum, n, m;
bool st[N];
// 插入邻接表头指针
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;     
}

bool prim()
{
    // n个点要进行n次
    for(int i = 1; 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(t != 1 && dist[t] == md)
            return false;

        if(t != 1) sum += dist[t];
        st[t] = true; // 这个点已经加进来了
        // 用找到的最小的点去更新距离
        for(int j = h[t]; j != -1; j = ne[j])
        {
            int a = e[j]; // 头节点
            dist[a] = min(dist[a], w[t][a]);
        }
    }
    return true;
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);
    memset(dist, 0x3f, sizeof dist);
    memset(w, 0x3f, sizeof w);

    // 读取所有边
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if(w[a][b] == md) add(a, b), add(b, a);
        w[b][a] = w[a][b] = min(w[a][b], c);
    }

    if(prim()) cout << sum;
    else cout << "impossible";
    return 0;
}