/*Input：
6 10 1 2 6 1 3 1 1 4 5 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 4 6 2 5 6 6
Output：
V1-V3=1 V3-V6=4 V6-V4=2 V3-V2=5 V2-V5=3 最小权值和=15 */
#include<stdio.h> #include<string.h> #define INF 0x3f3f3f #define N 100 int lowcost[N];//标记是否在集合S中并协助找到集合S中元素到其他元素的最小值min int cost[N][N]; int path[N];//标记前驱 int n,m; int Prim() { int i,w,v; int ans=0; for(i=2;i<=n;++i) { lowcost[i]=cost[1][i]; path[i]=1; } path[1]=0; for(i=2;i<=n;++i) { int min=INF; for(w=2;w<=n;++w) { if(lowcost[w]<min&&lowcost[w]) { v=w; min=lowcost[w]; } } printf("V%d--V%d == %d\n",path[v],v,min); ans+=min; path[w]=v; lowcost[v]=0; for(w=2;w<=n;++w) { if(cost[v][w]<lowcost[w]) { lowcost[w]=cost[v][w]; path[w]=v; } } } return ans; } int main() { while(~scanf("%d%d",&n,&m)) { memset(cost,INF,sizeof(cost)); int i,a,b,c; for(i=0;i<m;++i) { scanf("%d%d%d",&a,&b,&c); cost[a][b]=c; cost[b][a]=c; } printf("最小权值和=%d\n",Prim()); } return 0; }