本文共 4805 字，大约阅读时间需要 16 分钟。
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.
在《迪克·范·戴克秀》的一集中，小里奇把他爸爸背上的雀斑连在一起，形成了一幅自由钟的图片。唉，其中一个雀斑变成了伤疤，所以他的雷普利的订婚失败了。把迪克的背想象成一架在不同(x,y)位置上有雀斑的飞机。你的工作是告诉里奇如何连接这些点以减少墨水的使用量。里奇通过在对之间画直线连接点，可能在线之间提起笔。当Richie完成时，从任何雀斑到任何其他雀斑必须有一系列连接的线。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.
第一行包含0 < n <= 100，迪克背上的雀斑数量。每个雀斑都有一条线;下面的每一行包含两个实数，表示雀斑的(x,y)坐标。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
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Comparator;class edge { int u, v; //每条边的两个端点 double cost; //权值 public edge() { } public edge(int u, int v, double cost) { this.u = u; this.v = v; this.cost = cost; } public int getU() { return u; } public void setU(int u) { this.u = u; } public int getV() { return v; } public void setV(int v) { this.v = v; } public double getCost() { return cost; } public void setCost(double cost) { this.cost = cost; }}public class Main { public static int[] father = new int[100]; public static ArrayList elist = new ArrayList<>(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ArrayList list = new ArrayList<>(); //存每个点的信息 int n = Integer.parseInt(br.readLine()); int m = n * (n - 1) / 2; //m是边数 for (int i = 0; i < n; i++) { //[1.0 1.0, 2.0 2.0, 2.0 4.0] list.add(br.readLine()); } for (int i = 0; i < n; i++) { //得到一个点的坐标 String[] s = list.get(i).split(" "); double x1 = Double.parseDouble(s[0]); double y1 = Double.parseDouble(s[1]); for (int j = i + 1; j < n; j++) { //得到另一个点的坐标 String[] ss = list.get(j).split(" "); double x2 = Double.parseDouble(ss[0]); double y2 = Double.parseDouble(ss[1]); //计算距离，并记录该边的左右端点，纳入elist中 edge e = new edge(); e.setU(i); e.setV(j); e.setCost(Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2))); elist.add(e); } } //[edge{u=0.0, v=1.0, cost=1.4142135623730951}, edge{u=0.0, v=2.0, cost=3.1622776601683795}, edge{u=1.0, v=2.0, cost=2.0}] double result = kruskal(n, m);//n是顶点个数 m是边数 返回最小生成树的边权之和 System.out.println(String.format("%.2f", result)); } private static double kruskal(int n, int m) { //n是顶点个数 m是边数 返回最小生成树的边权之和 double sum = 0; //sum所求边权之和 int numE = 0; // numE是当前生成树的边数 for (int i = 1; i <= n; i++) { //并查集初始化 father[i] = i; } //所有的边按边权从小到大排序 elist.sort(new Comparator () { @Override public int compare(edge e1, edge e2) { return e1.cost > e2.cost ? 1 : -1;// return (int) (e1.cost - e2.cost);//错误，有重复值的话并没有按照升序排列 } }); for (int k = 0; k < m; k++) { //枚举所有边 int fau = findFather(elist.get(k).u); //查询两个端点所在集合的根结点 int fav = findFather(elist.get(k).v); if (fau != fav) { //如果不在一个集合 father[fau] = fav; //合并集合，即把改变加入最小生成树// System.out.println(elist.get(k).getU()+"->"+elist.get(k).getV()); sum += elist.get(k).getCost();//该边的权值累加记录 numE++; //当前生成树的边数 if (numE == n - 1) break; //边数等于顶点数减1时结束 } } if (numE != n - 1) return -1; //无法连通 else return sum; } public static int findFather(int x) { while (x != father[x]) { x = father[x]; } return x; }} 转载地址：http://vtfgn.baihongyu.com/