数据结构实验之图论六：村村通公路【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\n",ans);
else printf("-1\n");
}
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;
}