# 九度OJ——1144Freckles

```#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;

typedef struct point{
double x;
double y;
}Vertex;

typedef struct edge{
int start;
int end;
double len;
}Edge;

struct cmp{
bool operator() (Edge e1,Edge e2){
return e1.len>e2.len;
}
};

const int MAX = 110;
int data[MAX],N;
double sum;
priority_queue<Edge,vector<Edge>,cmp> Q;
Vertex vertexes[MAX];

double Length(Vertex v1 ,Vertex v2)
{
double len_x = v1.x-v2.x;
double len_y = v1.y-v2.y;
return sqrt(len_x*len_x+len_y*len_y);
}

//查找操作
int Find(int root)
{
if(data[root] < 0){
return root;
}
return data[root] = Find(data[root]);
}

//并操作
void Union(int root1,int root2)
{
root1 = Find(root1);
root2 = Find(root2);
if(root1 == root2){
return;
}else if(root1 < root2){
data[root1] += data[root2];
data[root2] = root1;
N--;
}else{
data[root2] += data[root1];
data[root1] = root2;
N--;
}
}

double Kruskal()
{
double sum = 0;
while(!Q.empty()){
Edge e = Q.top();
Q.pop();
int root1 = e.start;
int root2 = e.end;
if(Find(root1) != Find(root2)){
sum += e.len;
Union(root1,root2);
}
if(N == 1){
break;
}
}
return sum;
}

int main()
{
while(cin>>N){
while(!Q.empty()){
Q.pop();
}
for(int i = 0 ; i < MAX ; i++){
data[i] = -1;
}
for(int i = 1 ; i <= N ; i++){
Vertex v;
cin>>v.x>>v.y;
vertexes[i] = v;
}
for(int i = 1 ; i <= N ; i++){
for(int j = i+1 ; j <= N ; j++){
Edge e;
e.start = i;
e.end = j;
e.len = Length(vertexes[i],vertexes[j]);
Q.push(e);
}
}
sum = Kruskal();
printf("%.2lf\n",sum);
}

return 0;
}```

0 条评论

• ### 04-树6 Complete Binary Search Tree (30分)

A Binary Search Tree (BST) is recursively defined as a binary tree which has the...

The Head Elder of the tropical island of Lagrishan has a problem. A burst of ...

• ### 寻找大富翁

题目描述 浙江桐乡乌镇共有n个人,请找出该镇上的前m个大富翁. 输入描述: 输入包含多组测试用例. 每个用例首先包含2个...

• ### P2946 [USACO09MAR]牛飞盘队Cow Frisbee Team

题目描述 After Farmer Don took up Frisbee, Farmer John wanted to join in the fun. He...

• ### 04-树6 Complete Binary Search Tree (30分)

A Binary Search Tree (BST) is recursively defined as a binary tree which has the...

• ### UVA 11039-Building designing【贪心+绝对值排序】 UVA11039-Building designing

UVA11039-Building designing Time limit: 3.000 seconds An architect wants to desi...

• ### HDU-1003 Max Sum(动态规划，最长字段和问题)

Max Sum Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J...

• ### LeetCode Weekly Contest 38解题思路

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### PAT 甲级 1068 Find More Coins（0，1背包）

1068. Find More Coins (30) 时间限制 150 ms 内存限制 65536 kB 代码长度限制 16000 B ...

• ### HDU 1074 Doing Homework(状压DP)

Doing Homework Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

### 活动推荐 