http://poj.org/problem?id=2560
本题跟其他题差不多,只不过节点的权重需要自己计算
Freckles
Time Limit:1000MS |
|
Memory Limit:65536K |
Description
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.
Input
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.
Output
Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles.
Sample Input
3
1.0 1.0
2.0 2.0
2.0 4.0
Sample Output
3.41
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1705139
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
NULL 博文链接:https://200830740306.iteye.com/blog/603493
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
NULL 博文链接:https://128kj.iteye.com/blog/1704752
NULL 博文链接:https://128kj.iteye.com/blog/1707218
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
1.把自己的污水排到河里V 2.把自己的污水送到右边> 3.把自己的污水送到左边
北大POJ初级-简单搜索 解题报告+AC代码
这份代码用C++实现了经典算法并查集,来源于poj题目1182
北大POJ初级题-数据结构:解题报告+AC代码
北大POJ2187-Beauty Contest 解题报告+AC代码
北大POJ3252-Round Numbers 解题报告+AC代码
北大POJ1416-Shredding Company 解题报告+AC代码