HDU 1875(最小生成树)
2024-10-19 01:31:07
因为是全连接图,所以也可以用最小生成树
这道题给边加了一个限制条件,(10<=x<=1000),所以可能不能全连通,需要判断
#include <cstdio>
#include <iostream>
#include <queue>
#include <cmath>
using namespace std; #define sf scanf
#define pf printf
#define debug printf("!\n")
#define blank printf("\n")
#define mem(a,b) memset(a,b,sizeof(a)) const int MaxN = ;
const int INF = <<; int p[MaxN]; int r[MaxN*MaxN],u[MaxN*MaxN],v[MaxN*MaxN];
double w[MaxN*MaxN]; int m,n,vex; struct point
{
int x,y;
}; point pt[]; int find(int x){return p[x]==x?x:p[x]=find(p[x]);} int cmp(const int a,const int b)
{
return w[a]<w[b];
} double kruskal()
{
double ans = ;
int i; for(i = ;i<n;i++) p[i] = i;
for(i = ;i<m;i++) r[i] = i; sort(r,r+m,cmp); for(i = ;i<m;i++)
{
int e = r[i];
int x = find(u[e]);
int y = find(v[e]);
if(x!=y)
{
ans+=w[e];
p[x] = y;
vex++;
}
}
return ans;
} double getD(point p1 ,point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
} int main()
{
int i,j,t;
sf("%d",&t);
while(t--)
{
mem(u,);
mem(v,);
mem(w,); m=;
vex = ; sf("%d",&n);
for(i = ;i<n;i++)
{
sf("%d%d",&pt[i].x,&pt[i].y);
} for(i = ;i<n;i++)
{
for(j=i+;j<n;j++)
{
double d = getD(pt[i],pt[j]);
if(d< || d>)
{
continue;
}
u[m] = i;
v[m] = j;
w[m++] = d;
}
} double ans = kruskal(); if(vex<n)
pf("oh!\n");
else
pf("%.1lf\n",ans*);
} return ;
}
最新文章
- Oracle并行添加主键的方法
- unity生成WP工程后ExtendedSplashImage显示不正确的问题
- HTML简明教程(一)
- http和socket通信的区别
- vs2008编译QT开源项目三国杀(五篇文章)
- codeforces.com/contest/325/problem/B
- Caused by: com.fasterxml.jackson.core.JsonParseException: Unrecognized token &#39;name&#39;: was expecting (&#39;true&#39;, &#39;false&#39; or &#39;null&#39;)
- HTTP2的新特性
- Gazebo機器人仿真學習探索筆記(二)基本使用說明
- Ubuntu 安装yii2 advanced版 遇到的坑
- 第一阶段——CentOS6_Python3.6.1笔记(尚学堂-Python基础快速入门)+ 【补充】麦子-Python程序入门与进阶
- mount挂载相关参数详解
- asp.net core webapi处理Post请求中的request payload
- 【原创】c++拷贝初始化和直接初始化的底层区别
- 加密的m3u8、ts文件合并
- mongodb创建用户(转发)
- Mac OS X 恢复 VMware Fusion 虚拟机中的 vmdk 文件
- logbak 配置相关
- PAT A1115 Counting Nodes in a BST (30 分)——二叉搜索树,层序遍历或者dfs
- AWK学习一例