hdu 1875 畅通工程再续

点击打开链接hdu 1875

/*
1思路：最小生成树+prime（模板题）
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define MAXN 110
#define INF 0xFFFFFFF

int t , c;
double ans;
double lowcost[MAXN];
double G[MAXN][MAXN];
struct Point{
    int x;
    int y;
}p[MAXN];

void init(){
    for(int i = 1 ; i <= c ; i++){
       for(int j = 1 ; j <= c ; j++){
         double tmp_x = (p[i].x-p[j].x)*(p[i].x-p[j].x);
         double tmp_y = (p[i].y-p[j].y)*(p[i].y-p[j].y);
         double tmp =  sqrt(tmp_x + tmp_y);
         if(tmp < 10 || tmp > 1000)
           G[i][j] = INF;
         else
           G[i][j] = tmp;
       }
    }
}

void Prime(){
     int pos;
     double min;
     int vis[MAXN];
     memset(vis , 0 , sizeof(vis));
     init();
     vis[1] = 1;
     ans = 0;
     for(int i = 1 ; i <= c ; i++)     
        lowcost[i] = G[1][i];
     for(int i = 1 ; i <= c ; i++){
        min = INF;
        for(int j = 1 ; j <= c ; j++){
           if(!vis[j] && min > lowcost[j]){
              pos = j;
              min = lowcost[j];
           }
        }
        if(min == INF)
          break;
        ans += min;
        vis[pos] = 1;
        for(int j = 1 ; j <= c ; j++){
           if(!vis[j] && lowcost[j] > G[pos][j])
             lowcost[j] = G[pos][j];
        }
     }
     if(G[1][c] != INF)
       printf("%.1lf\n" , ans*100);
     else
       printf("oh!\n");
}

int main(){
   // freopen("input.txt" , "r" , stdin);
    scanf("%d" , &t);
    while(t--){
       scanf("%d" , &c);
       for(int i = 1 ; i <= c ; i++) 
          scanf("%d%d" , &p[i].x , &p[i].y);
       Prime();
    }
    return 0;
}