HDU 1162 Eddy's picture (最小生成树)(java版)

Eddy‘s picture

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1162

    ——每天在线,欢迎留言谈论。

题目大意:

给你N个点,求把这N个点连在一起的最短总距离。

思路:

假设每两两点之间都有路径,求最小生成树。

AC代码:(Java)

 1 import java.util.Scanner;
 2 import java.math.*;
 3 public class Main {
 4     public static final int MAXN = 110;
 5     public static double mp[][] = new double[MAXN][MAXN];
 6     public static Point p[] = new Point[MAXN];
 7     public static int n;
 8     public static String answer = new String();
 9     public static Scanner scn = new Scanner(System.in);
10     public static void main(String[] args){
11         for (int i = 0; i < MAXN; i++){
12             p[i] = new Point();
13         }
14         while (scn.hasNext()) {
15             n = scn.nextInt();
16         foundMap();
17         answer = String.format("%.2f", prim());
18         System.out.println(answer);
19         }
20         System.exit(0);
21     }
22     public static boolean foundMap() {
23         double x,y;
24         for (int i = 0; i < n; i++) {
25             x = scn.nextDouble();
26             y = scn.nextDouble();
27             p[i].setPoint(x, y);
28         }//Found points
29         for (int i = 0; i < n; i++)
30             for (int j = 0; j < n; j++)
31                 if (i != j)
32                     mp[i][j] = Point.getDistencs(p[i], p[j]);
33         //Found map
34         return true;
35     }
36     public static double prim() {
37         int tempI;
38         double tempClos;
39         double[] closEdge = new double[MAXN];
40         double sum = 0.0;
41         //Init closeEdge
42         closEdge[0] = 0.0;
43         for (int i = 1; i < n; i++) {
44             closEdge[i] = mp[0][i];
45         }
46         //Find n-1 edge
47         for (int i = 1; i < n; i++) {
48             tempI = -1;
49             tempClos = -1.0;
50             for (int j = 0; j < n; j++) {
51                 if (closEdge[j] != 0.0 && (tempClos == -1.0 || closEdge[j] < tempClos)){
52                     tempClos = closEdge[j];
53                     tempI = j;
54                 }
55             }
56             sum += tempClos;
57             closEdge[tempI] = 0;
58             for (int j = 0; j < n; j++) {
59                 if (j != tempI && closEdge[j] > mp[tempI][j]) {
60                     closEdge[j] = mp[tempI][j];
61                 }
62             }
63         }
64         return sum;
65     }
66 }
67 class Point { //已下为一个点类 可以不看。
68     private double x;
69     private double y;
70     public Point(double x,double y) {
71         this.x = x;
72         this.y = y;
73     }
74     public Point() {
75         x = 0.0;
76         y = 0.0;
77     }
78     public void setPoint(double X,double Y) {
79         this.x = X;
80         this.y = Y;
81     }
82     public double getX() {
83         return x;
84     }
85     public double getY() {
86         return y;
87     }
88     public static double getDistencs(Point p1,Point p2) {
89         return Math.sqrt(Math.pow(p1.getX() - p2.getX(), 2.0) + Math.pow(p1.getY() - p2.getY(),2.0));
90     }
91 }

2017-07-23 13:07:39

HDU 1162 Eddy's picture (最小生成树)(java版)

时间: 07-22

HDU 1162 Eddy's picture (最小生成树)(java版)的相关文章

hdu 1162 Eddy&#39;s picture 最小生成树入门题 Prim+Kruskal两种算法AC

Eddy's picture Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7428    Accepted Submission(s): 3770 Problem Description Eddy begins to like painting pictures recently ,he is sure of himself to

hdu 1162 Eddy&#39;s picture(最小生成树算法)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1162 Eddy's picture Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6866    Accepted Submission(s): 3469 Problem Description Eddy begins to like p

HDU 1162 Eddy&#39;s picture【最小生成树,Prime算法+Kruskal算法】

Eddy's picture Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9334    Accepted Submission(s): 4711 Problem Description Eddy begins to like painting pictures recently ,he is sure of himself to

HDU 1162 Eddy&#39;s picture(图论-最小生成树)

题目如下: Eddy's picture Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7267    Accepted Submission(s): 3676 Problem Description Eddy begins to like painting pictures recently ,he is sure of himse

hdu 1162 Eddy&#39;s picture(最小生成树)

Problem Description Eddy begins to like painting pictures recently ,he is sure of himself to become a painter.Every day Eddy draws pictures in his small room, and he usually puts out his newest pictures to let his friends appreciate. but the result i

hdu 1162 Eddy&#39;s picture (Kruskal算法,prim算法,最小生成树)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1162 [题目大意] 给你n个点的坐标,让你找到联通n个点的一种方法,保证联通的线路最短,典型的最小生成树问题. 方法一 , 通过不断找到最小的边来找到最终结果. Kruskal 算法 #include <iostream> #include <algorithm> #include <cstdio> #include <cmath> using namespac

HDU 1162 Eddy&#39;s picture (最小生成树 prim)

题目链接 Problem Description Eddy begins to like painting pictures recently ,he is sure of himself to become a painter.Every day Eddy draws pictures in his small room, and he usually puts out his newest pictures to let his friends appreciate. but the res

hdoj 1162 Eddy&#39;s picture(最小生成树)

Eddy's picture http://acm.hdu.edu.cn/showproblem.php?pid=1162 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7521    Accepted Submission(s): 3821 Problem Description Eddy begins to like painti

hdu 1162 Eddy&#39;s picture

最小生成树裸题,没有初始化都能AC,看来测试数据只有一组 #include<iostream> #include<vector> #include<cmath> #include<cstdio> #define inf 1<<30 #define maxn 105 using namespace std; struct stu { double x,y; }; stu mapp[maxn]; int n; vector<int>roo