最小生成树prim
原理参见上篇
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 8 const int INF = 99999999 ; 9 const int maxn = 105 ; 10 11 int map[maxn][maxn]; 12 int visit[maxn]; 13 int low[maxn]; 14 15 int main (){ 16 int n; 17 while (~scanf ("%d",&n)&&n){ 18 for (int i=0;i<n;i++) 19 for (int j=0;j<n;j++) 20 map[i][j]=INF; 21 for (int i=0;i<n-1;i++){ 22 char c[10]; 23 int a,b; 24 scanf ("%s%d",c,&a); 25 while (a--){ 26 scanf ("%s%d",c,&b); 27 map[i][(int)(c[0]-'A')]=map[(int)(c[0]-'A')][i]=b; 28 }//cout<<n<<" "<<i<<endl; 29 } 30 memset (visit,0,sizeof visit); 31 int ans=0; 32 int mi; 33 int pos=1; 34 visit[1]=1; 35 for (int i=0;i<n;i++) 36 low[i]=map[pos][i]; 37 for (int i=0;i<n-1;i++){ 38 mi=INF; 39 for (int j=0;j<n;j++) 40 if (!visit[j]&&low[j]<mi){ 41 mi=low[j];pos=j; 42 } 43 ans+=mi;visit[pos]=1; 44 for (int j=0;j<n;j++) 45 if (!visit[j]) 46 low[j]=min (low[j],map[pos][j]); 47 } 48 printf ("%d ",ans); 49 } 50 return 0; 51 }