Hdoj 1875.畅通工程再续 题解
2024-09-16 16:41:07
Problem Description
相信大家都听说一个“百岛湖”的地方吧,百岛湖的居民生活在不同的小岛中,当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖,发展首先要解决的问题当然是交通问题,政府决定实现百岛湖的全畅通!经过考察小组RPRush对百岛湖的情况充分了解后,决定在符合条件的小岛间建上桥,所谓符合条件,就是2个小岛之间的距离不能小于10米,也不能大于1000米。当然,为了节省资金,只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。
Input
输入包括多组数据。输入首先包括一个整数T(T <= 200),代表有T组数据。
每组数据首先是一个整数C(C <= 100),代表小岛的个数,接下来是C组坐标,代表每个小岛的坐标,这些坐标都是 0 <= x, y <= 1000的整数。
Output
每组输入数据输出一行,代表建桥的最小花费,结果保留一位小数。如果无法实现工程以达到全部畅通,输出”oh!”.
Sample Input
2
2
10 10
20 20
3
1 1
2 2
1000 1000
Sample Output
1414.2
oh!
Author
8600
Source
思路
最小生活树的算法,这里采用的是Kruskal算法
检验是否存在最小生成树只要判断图中连通块的个数,这个可以利用并查集计算
代码
#include<bits/stdc++.h>
using namespace std;
int father[110];
struct Graph
{
int u;
int v;
double dis;
}maps[10010];
int x[110],y[110];//存放坐标
void init(int n)
{
for(int i=1;i<=n;i++) father[i]=i;
}
int find(int x)
{
while(father[x]!=x) x=father[x];
return x;
}
void join(int a,int b)
{
int t1=find(a);
int t2=find(b);
if(t1!=t2) father[t1]=t2;
}
int main()
{
int t;
cin >> t;
while(t--)
{
int c;
cin >> c;
for(int i=1;i<=c;i++)
cin >> x[i] >> y[i];
int edgeNum = 0;
for(int i=1;i<=c-1;i++)
for(int j=i+1;j<=c;j++)
{
double tmp = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
if(tmp>=10.0 && tmp<=1000.0)
{
maps[++edgeNum].u = i;
maps[edgeNum].v = j;
maps[edgeNum].dis = tmp;
}else continue;
}
init(c);
sort(maps+1,maps+1+edgeNum,[](Graph x,Graph y)->bool{return x.dis < y.dis;});
double distance = 0.0;
for(int i=1;i<=edgeNum;i++)
if(find(maps[i].u) != find(maps[i].v))
{
join(maps[i].u,maps[i].v);
distance += maps[i].dis;
}
int cnt = 0;
for(int i=1;i<=c;i++)
{
if(father[i]==i) cnt++;
}
if(cnt<=1)
printf("%.1lf\n",distance*100.0);
else
cout << "oh!\n";
}
return 0;
}
最新文章
- 数据分页处理系列之三:Neo4j图数据分页处理
- 递归O(NlgN)求解逆序数
- Code Snippet
- JavaScript的for循环编写九九乘法表
- math对象和date对象
- sendBroadcast 无法接收
- quartz源码解析(一)
- 给自己加油,一定要学会MFC!
- Xcode5和6共处,如何发布应用程序存储
- MySql 修改外键 支持级联删除
- Intellij Idea搭建Spark开发环境
- 禁用Visual Studio 2013的Browser Link功能 -调试不断请求http://localhost:6154/c4ad1c693ebf428283832eaa827f9c6e/arterySignalR/poll?transport=longPolling...
- php <;a href>;<;/a>;链接地址中是php变量,链接文本也是php变量的代码处理方法
- 服务器php启动
- Tkinter Anchors(锚)
- SUSE11SP3--安装svn
- PMPBOK 进度管理
- MySQL-checkpoint技术
- Eclipse Tomcat部署项目没有加载新加的静态资源文件
- 辛星浅析raid