数据结构实验之图论六：村村通公路【Prim算法】（SDUT 3362）

题解：选点，选最小权的边，更新点权。可以手动自行找一遍怎么找到这个最小的生成树，随便选一个点放入我们选的集合中，然后看和这个点相连的点中，与那个点相连的那条边权值是最小的，选择之后，把相连的这个点一起放入集合中，这样的话集合中就多了一点，现在要找和这两个点都相连的点中，那个边的权最小，直到全部的点都在集合中就完成了。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int inf = 0x3fffff;
int gra[1005][1005];
int vis[1005];
int dist[1005];
void prim(int n)
{
    memset(vis,0,sizeof(vis));
    for(int i = 0; i <= n; i ++) dist[i] = gra[1][i];
    int Min = inf, v, flag = 1;
    for(int i = 1; i <= n; i ++)
    {
        Min = inf;
        for(int j = 1; j <= n; j ++)
        {
            if(!vis[j] && dist[j] < Min){
                Min = dist[j];
                v = j;
            }
        }
        if(Min == inf) {flag = 0;break;}
        vis[v] = 1;
        for(int j = 1; j <= n; j ++)
        {
            if(!vis[j] && dist[j] > gra[v][j]){
                dist[j] = gra[v][j];
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n;i ++)
    {
        ans += dist[i];
    }
    if(flag)printf("%d
",ans);
    else printf("-1
");
}
int main()
{
    int n,m,u,v,w;
    while(~scanf("%d%d",&n,&m)){
        for(int i = 0; i<= n; i ++)
        {
            for(int j = 0; j <= n; j ++)
            {
                if(i == j) gra[i][j] = 0;
                else gra[i][j] = inf;
            }
        }
        for(int i = 0; i < m; i ++)
        {
            scanf("%d%d%d",&u,&v,&w);
            gra[u][v] = gra[v][u] = w;
        }
        prim(n);
    }
    return 0;
}