最小生成树

acwing的prim板子题
题解
hdu1233还是畅通工程
最小生成树
prim写法，
先任取一点，找到距离该点最近的点加入集合中，反复进行这项操作，，就和最短路中的dijkstra算法很想了，只是不用进
行“松弛操作”，prime不需要更新所有到起点的距离,其实就是dijkstra的简化版，dijkstra
y总的最短路 ————
本人之前写的最短路题

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>

using namespace std ;

const int N = 110,INF = 1e8 ;
int g[N][N] ;  //存储图
int dist[N] ;  //存储距离
bool st[N] ;   //存储该点是否被加入集合
int n ;

int prim(){
    memset(st,0,sizeof st) ;
    for(int i = 0 ; i <= n ; i++){
        dist[i] = INF ;           //初始化
    }
    dist[1] = 0 ;

    int res = 0 ;
    for(int i = 0 ; i < n ; i++){
        int mind = INF , id = -1 ;
        for(int  j = 1 ; j <= n ;j++){
            if(!st[j] && mind > dist[j]){      //找到距离最小的点
                mind = dist[j] ;
                id = j ;
            }
        }
        st[id] = 1;
        res += dist[id] ;                //更新结果
        for(int j = 1 ; j <= n ; j++){
            if(!st[j]){
                dist[j] = min(g[id][j] , dist[j]) ;      //更新j点到该集合的最小距离
            }
        }
    }
    return res ;
}

int main(){
    while(cin >> n,n ){
        int m = n * (n - 1) / 2  ;
        for(int i =0 ; i < m ; i++){
            int a,b,c ;
            cin >> a >> b >> c ;
            g[a][b] = g[b][a] = c ;
        }

        cout << prim() << endl  ;
    }
}

第二种写法
kruskal

这种算法用到了两个关键的技术
1.排序，对每个边进行排序
2.判断圈，也就是处理联通性问题，这里使用并查集，，不会并查集请看
并查集

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std ;

struct edge{  //存边
    int a,b,v ;
    bool operator < (const edge x) const{
        return v < x.v ;
    }
};
const int N = 110 ;
int p[N] ;  //实现并查集
vector<edge> b ;   //存边
int n,m ;

int find(int x){
    if(x != p[x]) p[x] = find(p[x]) ;  //并查集
    return p[x] ;
}

void marge(int a,int b){
    int fa = find(a) ;
    int fb = find(b) ;  //并查集合并操作
    if(fa != fb){
        p[fa] = fb ;
    }
}

void kruskal(){
    for(int i = 0 ; i <= n ; i++){
        p[i] = i ;                 //并查集初始化
    }

    sort(b.begin(),b.end()) ;       //排序
    int res = 0 ;
    for(size_t i = 0 ; i < b.size() ; i ++){
        int sa = b[i].a , sb = b[i].b ;
        if(find(sa) != find(sb)){        //遍历，如果不连通就更新，合并
            res += b[i].v ;
            marge(sa,sb) ;
        }
    }
    cout << res << endl ;
}

int main(){
    while(cin >> n , n){
        b.clear() ;
        m = n * ( n - 1 ) / 2 ;
        for(int i = 0 ; i < m ; i++){
            int x,y,z ;
            cin >> x>>y >> z ;
            b.push_back({x,y,z}) ;
        }

        kruskal() ;
    }
}