畅通工程再续

http://acm.hdu.edu.cn/showproblem.php?pid=1875

kruskal算法： 140MS

View Code

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<math.h>
 4 struct node
 5 {
 6     int x, y ;
 7     double z ;
 8 }b[6000] ;
 9 int set[101], i ;
10 double sum ;
11 int cmp(const void *a, const void *b)
12 {
13    struct node *p1, *p2 ;
14    p1 = (struct node*)a ;
15    p2 = (struct node*)b ;
16    return p2->z > p1->z ? -1 : 1 ;
17 }
18 int find(int x)
19 {
20     if(set[x]!=x)
21     set[x] = find(set[x]) ;
22     return set[x] ;
23 }
24 void merge(int x,int y)
25 {
26     int fx,fy;
27     fx=find(x);
28     fy=find(y);
29     if(fx!=fy)
30     {
31         set[fx]=fy;
32         sum+=b[i].z;
33     }
34 }
35 int main()
36 {
37     int t,c,j,k,cnt;
38     int a[101][2];
39     double s;
40     scanf("%d",&t);
41     while(t--)
42     {
43         scanf("%d",&c);
44         for(i=0;i<c;i++)
45         scanf("%d%d",&a[i][0],&a[i][1]);
46         for(i=0;i<c;i++)
47         set[i]=i;
48         k=0; s=0;
49         for(i=0; i<c; i++)
50         for(j=i+1; j<c; j++)
51             {
52                s=sqrt((a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1]));
53                if(s>=10 && s<=1000)
54                  {
55                     b[k].x=i;
56                     b[k].y=j;
57                     b[k].z=s;
58                     s=0;
59                     k++;
60                  }
61             }
62           qsort(b,k,sizeof(b[0]),cmp);
63           sum=0;
64           for(i=0;i<k;i++)
65           merge(b[i].x,b[i].y);
66           cnt=0;
67           for(i=0;i<c;i++)
68           if(set[i]==i)
69           cnt++;
70           if(cnt==1)
71           printf("%.1lf\n",100*sum);
72           else
73           printf("oh!\n");
74     }
75     return 0 ;
76 }

prim算法：15MS

View Code

 1 #include<stdio.h>
 2 #include<math.h>
 3 #define N 110
 4 #define max 9999999
 5 double g[N][N];
 6 void prim(int n)
 7 {
 8     int i,j,u,flag,mark[N];
 9     double dis[N],cost,min;
10     for(i=0;i<n;i++)
11     {
12         mark[i]=0;
13         dis[i]=g[0][i];
14     }
15     mark[0]=1;
16     cost=0;
17     flag=1;
18     for(i=1;i<n;i++)
19     {
20         min=max;
21         for(j=1;j<n;j++)
22             if(!mark[j]&&min>dis[j])
23             {
24                 u=j;
25                 min=dis[j];
26             }
27         if(min==max||min<10)
28         {
29             flag=0;
30             break;
31         }
32         mark[u]=1;
33         cost+=min;
34         for(j=1;j<n;j++)
35             if(!mark[j]&&dis[j]>g[u][j])
36                 dis[j]=g[u][j];
37     }
38     if(flag)
39         printf("%.1f\n",100*cost);
40     else
41         printf("oh!\n");
42 }
43 int main()
44 {
45     int i,j,m,n,x[N],y[N];
46     double dis,x2,y2;
47     scanf("%d",&m);
48     while(m--)
49     {
50         scanf("%d",&n);
51         for(i=0;i<n;i++)
52             scanf("%d%d",&x[i],&y[i]);
53         for(i=0;i<n;i++)
54             for(j=0;j<=i;j++)
55             {
56                 x2=(x[i]-x[j])*(x[i]-x[j]);
57                 y2=(y[i]-y[j])*(y[i]-y[j]);
58                 dis=sqrt(x2+y2);
59                 if(dis<10||dis>1000)
60                     g[j][i]=g[i][j]=max;
61                 else
62                     g[i][j]=g[j][i]=dis;
63             }
64         prim(n);
65     }
66     return 0;
67 }