#include <cstdio>#include <algorithm>#include <cstring>#define MAX 110#define INF 1000000000using namespace std ;struct Edge{int x,y,w;}edge[MAX];int f[MAX] ;bool cmp(const Edge &a ,const Edge &b){return a.w<b.w ;}void init(){for(int i = 0 ; i < MAX; ++i){f[i] = i ; }}int find(int x){int r = x ;while(r != f[r]){r = f[r] ;}int temp ;while(x != r){temp = f[x] ;f[x] = r ;x = temp ;}return r ;}int kruskal(int n , int m){int lowcost[MAX];bool visited[MAX] ;memset(visited,false,sizeof(visited)) ;sort(edge,edge+n,cmp);for(int i = 0 ; i <= m ; ++i){lowcost[i] = INF ;}int index = 0 ;init() ;for(int i = 0 ; i < n ; ++i){int fx = find(edge[i].x) , fy = find(edge[i].y) ;if(fx != fy){lowcost[index++] = edge[i].w ;f[fx] = fy ;}}int sum = 0 ;for(int i = 0 ; i < m-1 ; ++i){if(lowcost[i] == INF){return INF ;}else{sum += lowcost[i] ;}}return sum ;}int main(){int n , m ;while(~scanf("%d%d",&n,&m) && n){for(int i = 0 ; i < n ; ++i){int x , y , w ;scanf("%d%d%d",&x,&y,&w) ;edge[i].x = x ;edge[i].y = y ;edge[i].w = w ;}int sum = kruskal(n,m) ;if(sum == INF){puts("?");}else{printf("%d\n",sum) ;}}return 0 ;}prim算法代码：#include <stdio.h>#include <string.h>#define MAX 110#define INF 1000000000int graph[MAX][MAX] ,visited[MAX] ;int prim(int m){int lowcost[MAX] , closest[MAX];for(int i = 1 ; i <= m ; ++i){closest[i] = 1 ;lowcost[i] = graph[1][i] ;}lowcost[1] = 0 ;memset(visited,false,sizeof(visited)) ;visited[1] = true ; for(int i = 0 ; i < m-1 ; ++i){int min = INF , index=0 ;for(int j = 1 ; j <= m ; ++j){if(!visited[j] && lowcost[j]<min){min = lowcost[j] ;index=j ;}}visited[index] = true ;for(int j = 1 ; j <= m ; ++j){if(!visited[j] && lowcost[j]>graph[index][j]){lowcost[j] = graph[index][j] ;closest[j] = index ;}}}int sum = 0 ;for(int i = 1 ; i <= m ; ++i){if(lowcost[i] == INF){return INF ;}sum += lowcost[i] ;}return sum ;}int main(){int n , m ;while(~scanf("%d%d",&n,&m) && n){for(int i = 0 ; i <= m ; ++i){for(int j = 0 ; j <= i ; ++j){graph[i][j] = graph[j][i] = INF ;}}for(int i = 0 ; i < n ; ++i){int x , y , w ;scanf("%d%d%d",&x,&y,&w);graph[x][y] = graph[y][x] = w ;}int sum = prim(m) ;if(sum == INF){puts("?");}else{printf("%d\n",sum) ;}}return 0 ;}
，每个人的生命都是可以绽放美丽，只要你珍惜。
