【最小生成树】A MST Problem - 木东驿站 - Powered by MoodBlog

CONTENT

【最小生成树】A MST Problem

题目描述

It is just a mining spanning tree ( 最小生成树 ) problem, what makes you a little difficult is that you are in a 3D space.

输入

The first line of the input contains the number of test cases in the file. And t he first line of each case

contains one integer numbers n(0<n<30) specifying the number of the point . The n next n line s, each line

contain s Three Integer Numbers xi,yi and zi, indicating the position of point i.

输出

For each test case, output a line with the answer, which should accurately rounded to two decimals .

测试输入

2

2

1 1 0

2 2 0

3

1 2 3

0 0 0

1 1 1

测试输出

1.41

3.97

博主答案

import java.util.Scanner;
public class Main{
	public static void main(String args[]){
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		for(int i=0;i<n;i++){
			int t = scanner.nextInt();
			Node[] nodes = new Node[t];
			for(int j=0;j<t;j++){
				nodes[j] = new Node();
				nodes[j].x = scanner.nextInt();
				nodes[j].y = scanner.nextInt();
				nodes[j].z = scanner.nextInt();
			}
			for(int j=0;j<t;j++){
				for(int k=0;k<t;k++){
					if(k!=j){
						nodes[j].addNext(k,nodes[k].x,nodes[k].y,nodes[k].z);
					}
				}
			}
			double ans = prim(nodes);
			System.out.printf("%.2fn",ans);
		}
	}
	public static double prim(Node[] node){
		int l = 1;
		int[] queue = new int[node.length];
		node[0].used = true;
		double ans = 0;
		for(int i=1;i<node.length;i++){
			double min = Integer.MAX_VALUE;
			int t = 0;
			for(int j=0;j<l;j++){
				int n = queue[j];
				for(int k=0;k<node[n].l;k++){
					if(min>node[n].length[k]&&node[node[n].next[k]].used==false){
						t = node[n].next[k];
						min = node[n].length[k];
					}
				}
			}
			ans+=min;
			queue[l++] = t;
			node[t].used = true;
		}
		return ans;
	}
}
class Node{
	int l;
	double x;
	double y;
	double z;
	boolean used = false;
	int[] next = new int[999];
	double[] length = new double[999];
	public void addNext(int n,double x,double y,double z){
		double t;
		t = Math.sqrt(Math.pow(this.x-x, 2) + Math.pow(this.y-y, 2) + Math.pow(this.z-z, 2));
		next[l] = n;
		length[l] = t;
		l++;
	}
}


个快快 2018年03月12日 天气 晴

REMARKS

© 2018 MoodBlog 0.2 个快快 作品 | 参考主题: mathilda by fuzzz. | 鲁ICP备16047814号