Constructing Roads

北大2421

题意：输入一个数n,代表村庄数，然后输入n行n列的数组，第i行第j列代表第i个村庄与第j个村庄的距离。然后输入一个数m,接下来m行，每行代表某两个村庄之间的路已被修；

输出要修的最短距离，保证每两个村庄之间都可以直接或间接的联系。

View Code

 1 //2421C++
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<stdlib.h>
 5 
 6 #define Max 1005
 7 int n,a[Max][Max];
 8 int set[Max],f[Max][Max];
 9 struct PP
10 {
11     int d;
12     int u,v;
13 }b[Max];
14 int cmp(const void *a,const void *b)
15 {
16     struct PP *x,*y;
17     x=(struct PP *)a;
18     y=(struct PP *)b;
19     return x->d>y->d?1:-1;
20 }
21 
22 int find(int x)//查找X并压缩路径
23 {
24     int r,i;
25     r=x;
26     while(r!=set[r])
27     {
28         r=set[r];
29     }
30     while(x!=r)
31     {
32         i=set[x];
33         set[x]=r;
34         x=i;
35     }
36     return r;
37 }
38 
39 int main()
40 {
41     int m,i,j,k,x,y,f1,f2;
42     while(scanf("%d",&n)!=-1)
43     {
44         memset(f,0,sizeof(f));
45         memset(a,0,sizeof(a));
46         for(i=1;i<=n;i++)
47             set[i]=i;
48         for(i=1;i<=n;i++)
49         {
50             for(j=1;j<=n;j++)
51             {
52                 scanf("%d",&a[i][j]);
53             }
54         }
55         scanf("%d",&m);
56         for(i=1;i<=m;i++)
57         {
58             scanf("%d%d",&x,&y);
59             f[x][y]=1;f[y][x]=1;//将已修的路在二维空间里标记为1；
60             f1=find(x);
61             f2=find(y);
62             if(f1!=f2)
63                 set[f1]=f2;//判断两个根结点，并做处理
64         }
65         k=0;
66         for(i=1;i<n;i++)
67         {
68             for(j=i+1;j<=n;j++)
69             {
70                 b[k].d=a[i][j];//用结构体存储两村庄间的距离
71                 b[k].u=i;//记下两村庄的编号
72                 b[k].v=j;
73                 k++;
74             }
75         }
76         qsort(b,k,sizeof(b[0]),cmp);//对村庄间的距离进行从小到大排序
77         int totle=0;int p1,p2;
78         for(i=0;i<k;i++)
79         {
80             p1=b[i].u;
81             p2=b[i].v;
82             if(f[p1][p2]!=1)//判断这条路是否已修
83             {
84                 f1=find(p1);
85                 f2=find(p2);
86                 if(f1!=f2)//两村庄间的路未修并且不能通过其他方式到达，则加在totle上；
87                 {
88                     set[f1]=f2;
89                     totle+=b[i].d;
90                 }
91             }
92         }
93         printf("%d\n",totle);
94     }
95     return 0;
96     
97 }