2421.txt

一道acm的题目

1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 #define MAXN 110
 5 struct edge{
 6   int s;
 7   int e;
 8   int dis;
 9 }a[MAXN*60];
10 
11 int N,Q,pre[MAXN],rank[MAXN];
12 
13 void init(){
14   int i;
15   for(i=1;i<=N;i++){
16     pre[i]=-1;
17     rank[i]=1;
18   }
19 }
20 
21 int find(int i){
22   if(pre[i]==-1) return i;
23   else return pre[i]=find(pre[i]);
24 }
25 
26 void Union(int i,int j){
27   i=find(i);
28   j=find(j);
29   if(i==j) return;
30   int temp=rank[i]+rank[j];
31   if(rank[i]<rank[j]){
32     pre[i]=j;
33     rank[j]=temp;
34   }
35   else{
36     pre[j]=i;
37     rank[i]=temp;
38   }
39 }
40 int cmp(const void *c,const void *b){
41   return (*(edge*)c).dis-(*(edge*)b).dis;
42 }
43 int main(){
44   int i,j,k,temp;
45   int z,y,sum;
46   while(scanf("%d",&N)!=-1){ 
47     k=0;
48     for(i=1;i<=N;i++){
49       for(j=1;j<=i;j++) scanf("%d",&temp);
50       for(;j<=N;j++){
51         scanf("%d",&temp);
52         a[k].s=i;
53         a[k].e=j;
54         a[k].dis=temp;
55         k++;
56       }
57     }
58     qsort(a,k,sizeof(a[0]),cmp);
59     init();
60     scanf("%d",&Q);
61     while(Q--){
62       scanf("%d%d",&z,&y);
63       Union(z,y);
64     }
65     sum=0;
66     for(i=0;i<k;i++){
67       if(find(a[i].s)!=find(a[i].e)){
68         sum+=a[i].dis;
69         Union(a[i].s,a[i].e);
70       }
71     }
72     printf("%d\n",sum);
73   }    
74 }