SDUTACM 图结构练习——最小生成树

题目描述

 有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其他任意的城市。  

输入

 输入包含多组数据，格式如下。 第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n <= 100， m <=10000) 剩下m行每行3个正整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c。  

输出

 每组输出占一行，仅输出最小花费。

示例输入

3 2 1 2 1 1 3 1 1 0

示例输出

2 0

提示

  #include<stdio.h> #include<stdlib.h> #include<string.h> #define INF 100000; int k[101][101],lowc[10001],vis[10001]; int prim(int n) { int i,j,p; int min,sum=0; memset(vis,0,sizeof(vis)); vis[0]=1; for(i=1;i<n;i++) lowc[i]=k[0][i]; for(i=1;i<n;i++) { min=INF; p=-1; for(j=0;j<n;j++) { if(vis[j]==0&&min>lowc[j]) { min=lowc[j]; p=j; } } sum=sum+min; vis[p]=1; for(j=0;j<n;j++) { if(vis[j]==0&&lowc[j]>k[p][j]) lowc[j]=k[p][j]; } } return sum; } int main() { int n,m,i,j,a,b,w; while(scanf("%d%d",&n,&m)!=EOF) { for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(i==j) k[i][j]=0; else k[i][j]=INF; } } for(i=0;i<m;i++) { scanf("%d%d",&a,&b); scanf("%d",&w); if(k[a-1][b-1]>w) { k[a-1][b-1]=w; k[b-1][a-1]=w; } } printf("%d\n",prim(n)); } }