//直接用Prim
1
#include<iostream>
2using namespace std;
3struct Edge
4
{
5
int u;
6 int v;
7 int weight;
8
};
9struct GraphMatrix
10{
11 int adj[27][27];
12};
13
14void Prim(GraphMatrix & GM,Edge MST[],int n);
15
16int main()
17{
18 int i,j;
19 Edge MST[27];
20 GraphMatrix GM;
21
22 int n,m,w;
23 char u,v;
24
25 while(cin>>n && n!=0)
26
{
27 for(i=0;i<n;i++)
28 for(j=0;j<n;j++)
29 {
30 if(i==j) GM.adj[i][j]=0;
31 else GM.adj[i][j]=100;
32
}
33
34 for(i=0;i<n-1;i++)
35 {
36 cin>>u>>m;
37
38 for(j=0;j<m;j++)
39 {
40 cin>>v>>w;
41 GM.adj[i][v-u+i]=w;
42 GM.adj[v-u+i][i]=w;
43 }
44 }
45
46 Prim(GM,MST,n);
47 int minw=0;
48 for(i=0;i<n-1;i++)
49 minw+=MST[i].weight;
50 cout<<minw<<endl;
51 }
52 return 0;
53}
54
55void Prim(GraphMatrix & GM,Edge MST[],int n)
56{
57 int i,j,k;
58 int si,mi,ni,res;
59 si=0;
60 for(i=0;i<n-1;i++)
61 {
62 MST[i].u=si;
63 MST[i].v=i+1;
64 MST[i].weight=GM.adj[si][i+1];
65 }
66
67
68 for(i=0;i<n-1;i++)
69 {
70 //mi=FindMinEdge(MST,si);
71 mi=si;
72 res=100;
73 for(j=si;j<n-1;j++)
74 {
75 if(MST[j].weight>0 && MST[j].weight<res)
76 {
77 res=MST[j].weight;
78 mi=j;
79 }
80 }
81 //swap
82 Edge tmp;
83 tmp=MST[mi];
84 MST[mi]=MST[si];
85 MST[si]=tmp;
86 //si++
87 si++;
88 //adjust
89 ni=MST[si-1].v;
90 for(j=si;j<n-1;j++)
91 {
92 k=MST[j].v;
93 if(GM.adj[ni][k]>0 && GM.adj[ni][k]<MST[j].weight)
94 {
95 MST[j].weight=GM.adj[ni][k];
96 MST[j].u=ni;
97 }
98 }
99
100 }
101}
102
103
posted on 2009-04-03 19:45
wyiu 閱讀(156)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ