首页 > 试题广场 >

Freckles

[编程题]Freckles

热度指数：9293 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad's back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley's engagement falls through. Consider Dick's back to be a plane with freckles at various (x,y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle.

输入描述:

    The first line contains 0 < n <= 100, the number of freckles on Dick's back. For each freckle, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the freckle.

输出描述:

    Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles.

示例1

输入

3
1.0 1.0
2.0 2.0
2.0 4.0

输出

3.41

算法知识视频讲解

健康快乐最重要

发表于 2020-02-22 08:45:01

一遍过，本题运用的kruskal的思想，通过并查集实现。获得两个点以及两个点间的距离，然后从集合中找出距离的最小值。加入到图的集合中，当把所有边都遍历完后，由于这个题，图肯定是连通的。所以只要记录加进来的边的长度(也就是两点间的距离就行）。 #include<iostream> #inc 展开全文

wbc990512

发表于 2021-01-26 13:06:29

题意：给出n个点和他们的坐标，用一支墨水笔将他们连通，要求墨水浪费最少典型的最小生成树问题，用kruskal问题（包括并查集） #include<stdio.h> #include<math.h> #include<stdlib.h> typedef struc 展开全文

爱喝零度可乐

发表于 2023-03-18 09:31:01

#include<cstdio> #include<vector> #include<algorithm> #include<math.h> #include<iostream> #define N 101 using namespace 展开全文

黄小鸭不会敲代码

发表于 2023-11-20 17:43:57

Kruskal算法，并查集，最小生成树把每个边按照权值排序，从小到大依次把一条边上的两个不在同一个连通分量的顶点加入最小生成树 #include <iostream> #include <vector> #include <algorithm> #include 展开全文

红颜为谁老fly

发表于 2024-06-07 13:47:54

// 克鲁斯卡尔算法 // 计算任意两点间的距离，并记录每条边，编号【0 - n-1】 // 对于边的集合进行排序，从小到大 // （克鲁斯卡尔算法）依次遍历所有边，使用并查集判断是否处于同一集合，不属于一个集合就记录该边 // 当连通分量=1时，输出 #include <iostream&g 展开全文