Eddy's picture
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1162
——每天在线，欢迎留言谈论。
题目大意：
给你N个点，求把这N个点连在一起的最短总距离。
思路：
假设每两两点之间都有路径，求最小生成树。
AC代码：（Java）
import java.util.Scanner;
import java.math.*;
public class Main {
public static final int MAXN = 110;
public static double mp[][] = new double[MAXN][MAXN];
public static Point p[] = new Point[MAXN];
public static int n;
public static String answer = new String();
public static Scanner scn = new Scanner(System.in);
public static void main(String[] args){
for (int i = 0; i < MAXN; i++){
p[i] = new Point();
}
while (scn.hasNext()) {
n = scn.nextInt();
foundMap();
answer = String.format("%.2f", prim());
System.out.println(answer);
}
System.exit(0);
}
public static boolean foundMap() {
double x,y;
for (int i = 0; i < n; i++) {
x = scn.nextDouble();
y = scn.nextDouble();
p[i].setPoint(x, y);
}//Found points
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j)
mp[i][j] = Point.getDistencs(p[i], p[j]);
//Found map
return true;
}
public static double prim() {
int tempI;
double tempClos;
double[] closEdge = new double[MAXN];
double sum = 0.0;
//Init closeEdge
closEdge[0] = 0.0;
for (int i = 1; i < n; i++) {
closEdge[i] = mp[0][i];
}
//Find n-1 edge
for (int i = 1; i < n; i++) {
tempI = -1;
tempClos = -1.0;
for (int j = 0; j < n; j++) {
if (closEdge[j] != 0.0 && (tempClos == -1.0 || closEdge[j] < tempClos)){
tempClos = closEdge[j];
tempI = j;
}
}
sum += tempClos;
closEdge[tempI] = 0;
for (int j = 0; j < n; j++) {
if (j != tempI && closEdge[j] > mp[tempI][j]) {
closEdge[j] = mp[tempI][j];
}
}
}
return sum;
}
}
class Point { //已下为一个点类 可以不看。
private double x;
private double y;
public Point(double x,double y) {
this.x = x;
this.y = y;
}
public Point() {
x = 0.0;
y = 0.0;
}
public void setPoint(double X,double Y) {
this.x = X;
this.y = Y;
}
public double getX() {
return x;
}
public double getY() {
return y;
}
public static double getDistencs(Point p1,Point p2) {
return Math.sqrt(Math.pow(p1.getX() - p2.getX(), 2.0) + Math.pow(p1.getY() - p2.getY(),2.0));
}
}
2017-07-23 13:07:39