本文共 3722 字，大约阅读时间需要 12 分钟。

import java.awt.Container;import java.util.ArrayList;import java.util.Collections;import java.util.Scanner;public class Main {	ArrayList
   
     list;	int c;	int[]x = new int[105];	int[]y = new int[105];	int []id;	public static void main(String[] args) {		new Main().run();	}	public void run() {		Scanner in = new Scanner(System.in);		int t = in.nextInt();		while(t-- > 0) {			c = in.nextInt();			id = new int[c+1];			for(int i = 0; i <= c; i++ )				id[i] = i;			for(int i = 1;i <= c; i++ ) {				x[i] = in.nextInt();				y[i] = in.nextInt();			}			list = new ArrayList<>();			for(int i = 1; i <= c; i++ ) {				for(int j = i+1; j<= c; j++ ) {					double d = getDistance(i, j);					if(d < 10 || d> 1000)						continue;					list.add(new Edge(i, j, d));				}			}			Collections.sort(list);			double sum = kruskal();			int cnt = 0;			for(int i = 1; i <= c; i++ ) {				if(i == id[i])					cnt++;			}			if(cnt > 1) {				System.out.println("oh!");			}			else {				System.out.printf("%.1f",sum*100);				System.out.println();			}					}			}	public double kruskal() {		double sum = 0;		for(int i = 0; i < list.size(); i++ ) {			Edge e = list.get(i);			int p = find(e.u);			int q = find(e.v);			if(p == q)				continue;			id[p] = q;			sum += e.w;		}		return sum;	}	public int find(int p) {		if(p == id[p])			return p;		else return id[p] = find(id[p]);	}			public double getDistance(int i, int j) {		return Math.sqrt(1.0*(x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));	}	}class Edge implements Comparable
    
     {	int u, v;	double w;	public Edge(int u, int v, double w) {		this.u = u;		this.v = v;		this.w = w;	}	public int compareTo(Edge o) {		return w > o.w ? 1 : -1;	}}
    
   

2、Prim

import java.util.ArrayList;	import java.util.LinkedList;	import java.util.PriorityQueue;	import java.util.Queue;	import java.util.Scanner;				public class Main {		ArrayList
   
     []adj;		int[]x = new int[105];		int[]y = new int[105];		boolean[]marked;		int t, c;		double INF = 999999.0;		double sum;		Queue
    
      pq;		public static void main(String[] args) {			new Main().run();		}		public void run() {			Scanner in = new Scanner(System.in);			t= in.nextInt();			while(t-- > 0) {				c = in.nextInt();				pq = new PriorityQueue();				marked = new boolean[c+1];				adj = new ArrayList[c+1];				for(int i = 1; i <= c; i++ ) {					adj[i] = new ArrayList<>();				}				for(int i = 1;i <= c; i++ ) {					x[i] = in.nextInt();					y[i] = in.nextInt();				}				for(int i = 1; i < c; i++ ) {					for(int j = i+1; j <= c; j++ ) {						double d = getDistance(i, j);						if(d < 10 || d > 1000) {							continue;						}						else {							adj[i].add(new Edge(i, j, d));							adj[j].add(new Edge(j, i, d));							//cnt[i]++; 可以用数组标记与其他顶点连接情况							//cnt[j]++ 当其与所有顶点都不连通时候 就输出oh！										//不满足 d < 10 || d > 1000视为不连通						}					}				}				prim();				}								}		public void prim() {			sum = 0;			visit(1);			//System.out.println("hello");			while(!pq.isEmpty()) {				Edge e = pq.poll();				int end = e.end;				if(marked[end])					continue;				sum += e.w;				if(!marked[end]) visit(end);							}//			System.out.println(sum);			if(sum != 0) {				System.out.printf("%.1f",sum*100);				System.out.println();			}			else {				System.out.println("oh!");			}					}		public void visit(int v) {			marked[v] = true;			for(Edge e:adj[v]) {				if(!marked[e.end]) {					pq.offer(e);				}			}		}		public double getDistance(int i, int j) {			return Math.sqrt(1.0*(x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));		}		}		class Edge implements Comparable
     
      {		int start, end;		double w;		public Edge(int start, int end, double w) {			this.start = start;			this.end = end;			this.w = w;		}		public int compareTo(Edge o) {			return w > o.w ? 1:-1;		}			}
     
    
   

转载地址：http://ilimi.baihongyu.com/