HDU 1102 Constructing Roads

 1 #include<iostream>
 2 #include<cstring>
 3 #include<stdio.h>
 4 #define MAX 101
 5 #define MAXINT 1000001
 6 using namespace std;
 7 int map[MAX][MAX],dis[MAX],m,n,luxian;
 8 bool visit[MAX];
 9 void prim()
10 {
11     memset(visit,false,sizeof(visit));
12     int i,j,MIN,k;luxian=0;
13     for(i=1;i<=n;i++) dis[i]=map[1][i];
14     visit[1]=true;
15     for(i=1;i<n;i++){
16         MIN=MAXINT;
17         for(j=2;j<=n;j++)
18             if(!visit[j] && dis[j]<MIN){
19                 MIN=dis[j];
20                 k=j;
21             }
22         visit[k]=true;
23         luxian+=MIN;
24         for(j=2;j<=n;j++)
25             if(!visit[j] && map[k][j]<dis[j]){
26                 dis[j]=map[k][j];
27             }
28     }
29 }
30 int main()
31 {
32     int i,j,x,y;
33     while(scanf("%d",&n)!=EOF){
34         for(i=1;i<=n;i++)
35             for(j=1;j<=n;j++)
36                 scanf("%d",&map[i][j]);
37         scanf("%d",&m);
38         for(i=1;i<=m;i++){
39             scanf("%d%d",&x,&y);
40             map[x][y]=map[y][x]=0;
41         }
42         prim();
43         printf("%d\n",luxian);
44     }
45 }