1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<string> 6 #include<vector> 7 #include<set> 8 #include<map> 9 #include<queue>10 #include<stack>11 using namespace std;12 const int inf=0xffffff;13 const int MAXN=21;14 int edges[MAXN][MAXN];15 int lowcost[MAXN];16 int nearvex[MAXN];17 int n,m;18 void prim(int u0)19 {20     int i,j;21     int sum=0;22     for(i=1;i<=n;i++)23     {24         lowcost[i]=edges[u0][i];25         nearvex[i]=u0;26     }27     nearvex[u0]=-1;28     for(i=1;i<n;i++)            //找出n-1个顶点 29     {30         int min=inf;31         int v=-1;32         for(j=1;j<=n;j++)33         {34             if(nearvex[j]!=-1&&lowcost[j]<min)35             {36                 v=j;37                 min=lowcost[j];38             }39         }40         if(v!=-1)41         {42             printf("%d %d %d\n",nearvex[v],v,lowcost[v]);43             nearvex[v]=-1;44             sum+=lowcost[v];45             for(j=1;j<=n;j++)46             {47                 if(nearvex[j]!=-1&&edges[v][j]<lowcost[j])48                 {49                     lowcost[j]=edges[v][j];50                     nearvex[j]=v;51                 }52             }53         }54     }55 }56 int main()57 {58     int i,j;59     int u,v,w;60     scanf("%d %d",&n,&m);61     memset(edges,0,sizeof(edges));62     for(i=1;i<=m;i++)63     {64         scanf("%d%d%d",&u,&v,&w);65         edges[u][v]=edges[v][u]=w;66     }67     for(i=1;i<=n;i++)68         for(j=1;j<=n;j++)69         {70             if(i==j)71                 edges[i][j]=0;72             else if(edges[i][j]==0)73                 edges[i][j]=inf;74         }75     prim(1);76     return 0;77 }