本文共 1901 字，大约阅读时间需要 6 分钟。

畅通工程再续

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 5382    Accepted Submission(s): 1595

#include<stdio.h>

#include<stdlib.h> #include<math.h> int father[103]; typedef struct Island{     int x;     int y;     double cost; }Island; int compare(const void *a,const void *b){     if((*(Island*)a).cost>(*(Island*)b).cost) return 1;     else if((*(Island*)a).cost<(*(Island*)b).cost) return -1;     else return 0; } Island land[5051]; int find(int x){     if(x!=father[x]){         find(father[x]);     }     else return x; } void unionset(int x,int y){     int a=find(x),b=find(y);     if(a<b) father[b]=a;     else father[a]=b; } int main(){     int t,c,i,num,count,j;     double cost;     int maze[103][2];     scanf("%d",&t);     while(t--){         for(i=0;i<103;i++){             father[i]=i;         }         count=0,cost=0,num=0;         scanf("%d",&c);         for(i=0;i<c;i++){             scanf("%d%d",&maze[i][0],&maze[i][1]);         }         for(i=0;i<c;i++){             for(j=i+1;j<c;j++){                 double dist=sqrt(1.0*(maze[i][0]-maze[j][0])*(maze[i][0]-maze[j][0])+(maze[i][1]-maze[j][1])*(maze[i][1]-maze[j][1]));                 if(dist>=10&&dist<=1000){                     land[num].x=i;                     land[num].y=j;                     land[num].cost=dist;                     num++;                 }             }         }         if(num<c-1){             printf("oh!\n");             continue;         }         qsort(land,num,sizeof(Island),compare);         for(i=0;i<num;i++){             if(find(land[i].x)!=find(land[i].y)){                 unionset(land[i].x,land[i].y);                 cost+=land[i].cost;                 count++;             }             if(count==c-1) break;         }         if(count==c-1) printf("%.1lf\n",cost*100);         else printf("oh!\n");     }     return 0; }

转载地址：http://uxtpi.baihongyu.com/