当前位置:网站首页>Blue Bridge Cup provincial match simulation question 9 (MST)
Blue Bridge Cup provincial match simulation question 9 (MST)
2022-07-05 08:51:00 【Qizi K】
Blue Bridge Cup provincial match simulation Question 9
Problem description
2015 year , All over China, household electricity has been realized . As a Power Builder , Xiao Ming is helping one belt, one road, the other country .
This time, , Xiao Ming wants to help n The village is electrified , among 1 A power station can be built in Village No , The electricity is enough for all the villages .
Now? , this n There are no wires between the villages , Xiao Ming's main task is to set up wires to connect these villages , So that all villages are directly or indirectly connected to power stations .
Xiao Ming measured the location of all the villages ( coordinate ) And height , If you want to connect two villages , Xiao Ming needs to spend the coordinate distance between the two villages plus the square of the height difference , Formally described as coordinates by (x_1, y_1) The height is h_1 The village and coordinates are (x_2, y_2) The height is h_2 The cost of the connection between villages is
sqrt((x_1-x_2)(x_1-x_2)+(y_1-y_2)(y_1-y_2))+(h_1-h_2)*(h_1-h_2).
In the upper form sqrt Denotes the square root in brackets . Notice the position of the brackets , The calculation method of height is different from that of abscissa and ordinate .
Because of the limited funds , Please help Xiao Ming calculate how much it will cost him to make this n All villages are electrified .
Input format
The first line of input contains an integer n , It means the number of villages .
Next n That's ok , Every three integers x, y, h, It means the horizontal of a village 、 Ordinates and heights , The first village could build a power station .
Output format
Output one line , Contains a real number , Rounding reservation 2 Decimal place , Answer .
The sample input
4
1 1 3
9 9 7
8 8 6
4 5 4
Sample output
17.41
Evaluate use case size and conventions
about 30% The evaluation case of ,1 <= n <= 10;
about 60% The evaluation case of ,1 <= n <= 100;
For all profiling use cases ,1 <= n <= 1000,0 <= x, y, h <= 10000.
tips: Bare minimum spanning tree . Note the data range , Go straight up Prim( Because the data is just 1000, And calculate the distance of each point , Use adjacency matrix directly +prim that will do , No heap optimization ( If the edge is still used kruskal Write mst)).
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int n,cnt,vis[1005];
struct node{
double x,y,h;
}book[1005];
double mp[1005][1005],dis[1005],sum;
double getdis(int i, int j){
return sqrt((book[i].x - book[j].x) * (book[i].x - book[j].x) + (book[i].y - book[j].y) * (book[i].y - book[j].y)) +
(book[i].h - book[j].h) * (book[i].h - book[j].h);
}
int main(){
scanf("%d",&n);
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j)
if(i == j) mp[i][j] = 0;
else mp[i][j] = inf;
}
for(int i = 1; i <= n; ++i)
scanf("%lf%lf%lf",&book[i].x,&book[i].y,&book[i].h);
for(int i = 1; i <= n; ++i){
for(int j = i + 1; j <= n; ++j)
mp[i][j] = mp[j][i] = getdis(i,j);
}
for(int i = 1; i <= n; ++i)
dis[i] = mp[1][i];
vis[1] = 1, cnt++;
//Prim
while(cnt < n){
int minn = inf,u;
for(int j = 1; j <= n; ++j){
if(!vis[j] && dis[j] < minn){
u = j,minn = dis[j];
}
}
vis[u] = 1,cnt++;
sum += dis[u];
for(int v = 1; v <= n; ++v){
if(!vis[v] && dis[v] > mp[u][v])
dis[v] = mp[u][v];
}
}
printf("%.2lf",sum);
return 0;
}
边栏推荐
- 【日常訓練--騰訊精選50】557. 反轉字符串中的單詞 III
- OpenFeign
- Guess riddles (9)
- Beautiful soup parsing and extracting data
- Wechat H5 official account to get openid climbing account
- Search data in geo database
- 12、动态链接库,dll
- Digital analog 1: linear programming
- Halcon: check of blob analysis_ Blister capsule detection
- Mathematical modeling: factor analysis
猜你喜欢
猜谜语啦(9)
[牛客网刷题 Day4] JZ55 二叉树的深度
Halcon color recognition_ fuses. hdev:classify fuses by color
Programming implementation of ROS learning 6 -service node
The combination of deep learning model and wet experiment is expected to be used for metabolic flux analysis
An enterprise information integration system
Guess riddles (3)
Guess riddles (6)
Halcon: check of blob analysis_ Blister capsule detection
IT冷知识(更新ing~)
随机推荐
Explore the authentication mechanism of StarUML
图解八道经典指针笔试题
Basic number theory - factors
The combination of deep learning model and wet experiment is expected to be used for metabolic flux analysis
Redis implements a high-performance full-text search engine -- redisearch
猜谜语啦(2)
C language data type replacement
Xrosstools tool installation for X-Series
Adaboost使用
特征工程
[牛客网刷题 Day4] JZ32 从上往下打印二叉树
How apaas is applied in different organizational structures
Mathematical modeling: factor analysis
Old Wang's esp8266 and old Wu's ws2818 light strip
MPSoC QSPI Flash 升级办法
[牛客网刷题 Day4] JZ55 二叉树的深度
Lori remote control LEGO motor
Illustration of eight classic pointer written test questions
猜谜语啦(3)
Ros-11 common visualization tools