1 /* 2 最小生成树，prim算法 3 */ 4 #include <cstdio> 5 #include <cstring> 6 #include <algorithm> 7  8 using namespace std; 9 const int N = 105;10 const int INF = 0x3f3f3f3f;11 12 int k , fa[N] , minn[N] , first[N] , vis[N];//vis[N]表示是否添入以保存的集合13 14 struct Edge{15     int y , next , d;16     bool operator<(const Edge & m )const{17         return d < m.d;18     }19 }e[N*N];20 21 void add_edge(int x , int y, int d)22 {23     e[k].y = y , e[k].next = first[x] , e[k].d = d;24     first[x] = k++;25 }26 27 int prim(int src , int n)28 {29     memset(minn , 0x3f , sizeof(minn));30     memset(vis , 0 , sizeof(vis));31     vis[src] = 1;32     for(int i = first[src] ; i!=-1 ; i=e[i].next)33     {34         int v = e[i].y;35         if(!vis[v]) minn[v] = min(minn[v] , e[i].d);36     }37     int ans = 0;38     for(int i = 1 ; i<n ; i++)39     {40         int index = 0 , Min = INF;41         for(int j = 1 ; j<=n ; j++)42         {43             if(minn[j] < Min){44                 Min = minn[j];45                 index = j;46             }47         }48         ans += Min;49         minn[index] = INF;50         vis[index] = 1; //使index不能再被访问51         //更新52         for(int j = first[index] ; j!=-1 ; j=e[j].next)53         {54             int v = e[j].y;55             if(!vis[v]) minn[v] = min(minn[v] , e[j].d);56         }57     }58     return ans;59 }60 61 int main()62 {63    // freopen("a.in" , "r" , stdin);64     int n , m , a , b , d;65     while(scanf("%d" , &n) , n)66     {67         m = n*(n-1) / 2;68         for(int i = 1 ; i<=n ; i++) fa[i] = i;69 70         k = 0;71         memset(first , -1 , sizeof(first));72         for(int i = 0 ; i<m ; i++){73             scanf("%d%d%d" , &a , &b , &d);74             add_edge(a , b , d);75             add_edge(b , a , d);76         }77 78         printf("%d\n" , prim(1 , n));79     }80     return 0;81 }

 1 /* 2 最小生成树，prim算法 3 */ 4 #include <cstdio> 5 #include <cstring> 6 #include <algorithm> 7  8 using namespace std; 9 const int N = 105;10 11 int k , fa[N];12 13 struct Edge{14     int x , y , d;15     bool operator<(const Edge & m )const{16         return d < m.d;17     }18 }e[N*N];19 20 void add_edge(int x , int y, int d)21 {22     e[k].x = x , e[k].y = y , e[k].d = d;23     k++;24 }25 26 int get_head(int x)27 {28     while(x != fa[x]) x=fa[x];29     return x;30 }31 32 bool Union(int x , int y)33 {34     int fa_x = get_head(x);35     int fa_y = get_head(y);36     if(fa_x != fa_y){37         fa[fa_x] = fa_y;38         return true;39     }40     return false;41 }42 43 int main()44 {45    // freopen("a.in" , "r" , stdin);46     int n , m , a , b , d;47     while(scanf("%d" , &n) , n)48     {49         k = 0;50         m = n*(n-1) / 2;51 52         for(int i = 1 ; i<=n ; i++) fa[i] = i;53 54         for(int i = 0 ; i<m ; i++){55             scanf("%d%d%d" , &a , &b , &d);56             add_edge(a , b , d);57         }58         sort(e , e+k);59         int ans = 0;60         for(int i = 0 ; i<k ; i++){61             if(Union(e[i].x , e[i].y)) ans += e[i].d;62         }63         printf("%d\n" , ans);64     }65     return 0;66 }