hdu 畅通工程再续
2024-10-19 22:28:06
http://acm.hdu.edu.cn/showproblem.php?pid=1875
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 1001
using namespace std;
const int inf=<<; int n;
double g[maxn][maxn];
bool vis[maxn];
double dis[maxn];
double sum;
bool flag=true; struct node
{
int x,y;
}p[maxn]; int sqr(int x)
{
return x*x;
} double dist(int x1,int y1,int x2,int y2)
{
return sqrt(sqr(x1-x2)+sqr(y1-y2));
} void prim()
{
memset(vis,false,sizeof(vis));
for(int i=; i<n; i++) dis[i]=g[][i];
dis[]=;
vis[]=true;
for(int i=; i<n; i++)
{
double m=(double)inf;
int x;
for(int y=; y<n; y++) if(!vis[y]&&dis[y]<m) m=dis[x=y];
if(m==inf){flag=false;break;}
sum+=m;
vis[x]=true;
for(int y=; y<n; y++) if(!vis[y]&&dis[y]>g[x][y]) dis[y]=g[x][y]; }
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=; i<; i++)
{
for(int j=; j<; j++)
{
if(i==j) g[i][j]=;
else
g[i][j]=g[j][i]=inf;
}
}
for(int i=; i<n; i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
}
for(int i=; i<n; i++)
{
for(int j=; j<n; j++)
{
if(i!=j){
double d=dist(p[i].x,p[i].y,p[j].x,p[j].y);
if(d>=10.0&&d<=1000.0) g[i][j]=d;
}
}
}
flag=true;
sum=0.0;
prim();
if(!flag) printf("oh!\n");
else
printf("%.1lf\n",(sum*));
}
return ;
}
最新文章
- Java中用内存映射处理大文件
- Apache Spark技术实战之6 -- spark-submit常见问题及其解决
- HDU 1171 Big Event in HDU --暴力+生成函数
- Android 利用Service实现下载网络图片至sdk卡
- linux strace
- oracle schema object
- svn 分支
- Analyzer使用第二Y轴,以及同一分析图不同量值使用不同的图形样式
- Algorithm: quick sort implemented in python 算法导论 快速排序
- IOC容器 - Autofac概述
- 【其他】MySql常用命令
- hdu_1790_The Balance(母函数)
- Let the Balloon Rise(水)
- linux 查看CPU、内存、磁盘信息命令
- 了解原型设计工具pencil project
- 移动web图片加载完获取img宽高
- jenkins的 git多分支自动构建
- 【XSY2715】回文串 树链剖分 回文自动机
- 文件内容统计:对任意给定的.txt文件进行内容的字符数、行数、单词数进行统计
- What is 软件工程
热门文章
- codevs1033 蚯蚓的游戏问题
- SPOJ694 -- DISUBSTR	后缀树组求不相同的子串的个数
- 将 Web 应用性能提高十倍的10条建议
- css(二)
- Apache HttpComponents Client 4.0快速入门/升级-2.POST方法访问网页
- Android Clipboard(复制/剪贴板)
- USB HID Report Descriptor 报告描述符详解
- http://msh.baidu.com/UTWpR6wY4722
- overcast
- 跨域访问-JSONP