我要啦免费统计
 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, 0sizeof(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 阅读(391) 评论(0)  编辑 收藏 引用 所属分类: pku

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理