最小生成树裸题 - prim题解 | #畅通工程#

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int d[N];
int g[N][N];
bool st[N];
int prim(){
    memset(st, 0, sizeof st);
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    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 || d[j] < d[t]))
                t = j;
        }

        st[t] = true;
        res += d[t];
        if(d[t] == INF) return d[t];
        for(int j = 1; j <= n; j ++){
            d[j] = min(d[j], g[t][j]);
        }
    }
    return res;

}


int main(){
    while(cin>>m>>n){
        if(!m) break;
        memset(g, 0x3f, sizeof g);
        for(int i = 1; i <= n; i ++) g[i][i] = 0;
        for(int i = 0; i < m; i ++){
            int x, y, z;
            cin>>x>>y>>z;
            g[x][y] = g[y][x] = min(g[x][y], z);
        }
        int t = prim();
        if(t == INF) puts("?");
        else cout<<t<<endl;
    }
    return 0;
}