hdu 4463 有一条边必须加上 (2012杭州区域赛K题)
2024-08-30 18:25:42
耐克店 和 苹果店必须相连
Sample Input
4
2 3
0 0
1 0
0 -1
1 -1
0
Sample Output
3.41
# 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[MAXN]; 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) ;
while(scanf("%d" , &n) != EOF)
{
if (n == )
break ;
int i , j ;
int pp , qq ;
scanf("%d %d" , &pp , &qq) ;
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)) ;
cost[i][j] = t ;
cost[j][i] = t ;
}
double k = cost[pp-][qq-] ;
cost[pp-][qq-] = ;
cost[qq-][pp-] = ;
k += Prim() ;
printf("%.2lf\n" , k) ; }
return ;
}
最新文章
- Flex 中画图工具(drawTool)失效
- 我的android学习经历9
- Python ValueError: IO operation on closed file
- Java设计模式——装饰者模式
- IoC 依赖注入、以及在Spring中的实现
- For Exam (Java常用设计模式) 介绍
- Python面向对象编程——引言
- Cocoa &; Cocoa Touch概念
- Ibatis.net防Sql注入
- Rotate Array 解答
- JFreeChart多坐标轴曲线图
- java面试题大全-基础方面
- [NOIP2012提高组] CODEVS 1200 同余方程(扩展欧几里德算法)
- Mysql ODBC 5.1 Driver免安装脚本
- DOM范围
- poj2342 Anniversary party
- 增加临时表空间组Oracle11g单实例
- SSM整合Shiro 身份验证及密码加密简单实现
- php 把数字转化为大写中文
- Linux启动与禁止SSH用户及IP的登录