1 /*
2 ID:dongyun1
3 TASK:agrinet
4 LANG: C++
5 */
6 #include<iostream>
7 //#include<fstream>
8 using namespace std;
9
10 #define N 101
11 int n;
12 int map[N][N],visited[N];
13
14
15 int main()
16 {
17 // ifstream fcin("agrinet.in");
18 // ofstream fcout("agrinet.out");
19 int i,j,k,sum=0,node;
20 int dist;
21
22 while(scanf("%d",&n)!=EOF){
23 // while(cin>>n) {
24
25 memset(visited,0,sizeof( visited));
26 memset( map, 0, sizeof(map));
27
28 for( i=0;i<n;i++)
29 for( j=0;j<n;j++)
30 scanf("%d",&map[i][j]);
31 //cin>>map[i][j];
32
33 sum=0;
34 visited[0]=1;
35
36 for( i=1;i<n;i++){
37 dist=0;
38 for(j=0;j<n;j++)
39 for( k=0;k<n;k++){
40 if( map[j][k] && visited[j] && !visited[k]){//printf("AAAAA\n");
41 if( dist == 0 || map[j][k]< dist){
42 dist = map[j][k];
43 node=k;
44 // printf("tag\n");
45 }
46 }
47 }
48 visited[node]=1;
49 sum+=dist;
50 }
51
52
53 //cout<<sum<<endl;
54 printf("%d\n",sum);
55 }
56 //system("pause");
57
58 return 0;
59 }
60 /*
61 4
62 0 4 9 21
63 4 0 8 17
64 9 8 0 16
65 21 17 16 0
66 2
67 0 2
68 3 0
69 3
70 0 1 2
71 2 0 1
72 2 2 0
73 4
74 0 4 9 21
75 4 0 8 17
76 9 8 0 16
77 21 17 16 0
78
79
80 */
81
簡單題 最小成樹
posted on 2008-10-11 15:22
爬 閱讀(428)
評論(0) 編輯 收藏 引用 所屬分類:
pku