hdu 1875 最小生成樹+并查集

暢通工程再續

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

Total Submission(s): 11905    Accepted Submission(s): 3648

Problem Description 相信大家都聽說一個“百島湖”的地方吧，百島湖的居民生活在不同的小島中，當他們想去其他的小島時都要通過劃小船來實作。現在政府決定大力發展百島湖，發展首先要解決的問題當然是交通問題，政府決定實作百島湖的全暢通！經過考察小組RPRush對百島湖的情況充分了解後，決定在符合條件的小島間建上橋，所謂符合條件，就是2個小島之間的距離不能小于10米，也不能大于1000米。當然，為了節省資金，隻要求實作任意2個小島之間有路通即可。其中橋的價格為 100元/米。  

Input 輸入包括多組資料。輸入首先包括一個整數T(T <= 200)，代表有T組資料。

每組資料首先是一個整數C(C <= 100),代表小島的個數，接下來是C組坐标，代表每個小島的坐标，這些坐标都是 0 <= x, y <= 1000的整數。

Output 每組輸入資料輸出一行，代表建橋的最小花費，結果保留一位小數。如果無法實作工程以達到全部暢通，輸出”oh!”.  

Sample Input

2
2
10 10
20 20
3
1 1
2 2
1000 1000
        

Sample Output

1414.2
oh!
        

Author 8600 題目真的比較水，但是自己竟然還是wA了好多次，原來是把1000看成了100，妹的，氣死我了

#include<stdio.h>'
#include<iostream>
#include<cstring>
#include<cmath>
#define M  1<<30
#define D 120
struct info
{
    double x;
    double y;
}unit[D];
double map[D][D];
int visit[D];
double dis[D];
int flag[D];
int num;
int find(int x)
{
    return flag[x]=(flag[x]==x?x:find(flag[x]));
}
void merge(int a,int b)
{
    int x=find(a);
    int y=find(b);
    if(x!=y)
    {
        flag[x]=y;
        num--;
    }

}

double prim(int n)
{
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        dis[i]=map[1][i];
    }
    dis[1]=0;
    for(j=1;j<=n;j++)
    {
       double t=M;
       int pos;
       for(i=1;i<=n;i++)
       {
           if(!visit[i]&&t>dis[i])
           {
               t=dis[i];
               pos=i;
           }
       }
       visit[pos]=1;
       for(i=1;i<=n;i++)
       {
           if(!visit[i]&&dis[i]>map[pos][i]&&map[pos][i]!=M)
			{
				dis[i]=map[pos][i];
				//printf("%d   %d\n",i,dis[i]);
			}

       }

    }
   double sum=0;
   /* for(i=1;i<=n;i++)
    {
        printf("%d\n",dis[i]);
    }*/
    for(i=1;i<=n;i++)
    sum=sum+dis[i];
    return sum;

}
int main()
{

    int i,j,k;
    int e,c;
    scanf("%d",&e);

      while(e--)
      {
       scanf("%d",&c);
       for(i=1;i<=c;i++)
       {
           scanf("%lf%lf",&unit[i].x,&unit[i].y);
       }
       for(i=1;i<=c;i++)
       {
           for(j=1;j<=c;j++)
           {
               map[i][j]=M;
           }

       }
        for(i=1;i<=c;i++)
        {
            flag[i]=i;
        }
       memset(visit,0,sizeof(visit));
       num=c-1;
       for(i=1;i<=c;i++)
       {
           for(j=1;j<=c;j++)
           if(i==j)
           map[i][j]=0;
           else
           {
double sum=sqrt((unit[i].x-unit[j].x)*(unit[i].x-unit[j].x)+(unit[i].y-unit[j].y)*(unit[i].y-unit[j].y));
             if((sum<=1000.0)&&(sum>=10.0))
               {

                 map[i][j]=sum;
                 map[j][i]=sum;
                // printf("%d %d\n",i,j);
                 merge(i,j);

               }
           }
       }
       if(num>0)
       {
           printf("oh!\n");
           continue;
       }
       double ans=prim(c);
       double h=ans*100.0;
       printf("%.1lf\n",h);

      }

    return 0;
}