用处

求最小生成树的权和时使用
稠密图
O(nm)

模板

Prim算法求最小生成树

#include
#include
#include

using namespace std;

const int N = 510,INF = 0x3f3f3f3f;

int dist[N];
int d[N][N];
bool st[N];
int n,m;

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],d[t][j]);

        st[t] = true; 
    }

    return res;
}

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

    memset(d,0x3f,sizeof d);

    while(m --){
        int a,b,c;
        cin >> a >> b >> c;
//无向图要双向联通
        d[a][b] = d[b][a] = min(d[a][b],c);
    }

    int t = prim();
    if(t == INF) cout << "impossible";
    else cout << t;
}