正文
hdu 1875 给出每个结点的坐标 权值为两点间的距离 (MST)
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
Sample Input
2
2
10 10 //坐标
20 20
3
1 1
2 2
1000 1000
Sample Output
1414.2 //最小权值和*100 保留1位小数
oh! //不连通
prim
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# define LL long long
using namespace std ; const int INF=0x3f3f3f3f;
const int MAXN=;
bool vis[MAXN];
double lowc[MAXN];
int n ;
double cost[MAXN][MAXN] ; struct poin
{
int x ;
int y ;
}p[]; double Prim()//点是0~n-1
{
double ans=;
memset(vis,false,sizeof(vis));
vis[]=true;
for(int i=;i<n;i++)lowc[i]=cost[][i];
for(int i=;i<n;i++)
{
double minc=INF;
int p=-;
for(int j=;j<n;j++)
if(!vis[j]&&minc>lowc[j])
{
minc=lowc[j];
p=j;
}
if(minc==INF)return -;//原图不连通
ans+=minc;
vis[p]=true;
for(int j=;j<n;j++)
if(!vis[j]&&lowc[j]>cost[p][j])
lowc[j]=cost[p][j];
}
return ans;
} int main()
{ // freopen("in.txt","r",stdin) ;
int T ;
scanf("%d" , &T) ;
while(T--)
{
scanf("%d" , &n) ;
int i , j ;
for (i = ; i < n ; i++)
for (j = ; j < n ; j++)
cost[i][j] = INF ;
for (i = ; i < n ; i++)
scanf("%d %d" , &p[i].x , &p[i].y) ;
for (i = ; i < n ; i++)
for (j = i+ ; j < n ; j++)
{
double t = sqrt((double)(p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y)) ;
if (t <10.0 || t > 1000.0)
continue ;
cost[i][j] = t ;
cost[j][i] = t ;
}
double k = Prim() ;
if (k == -)
printf("oh!\n") ;
else
printf("%.1lf\n" , k*) ; }
return ;
}