Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- import java.lang.Math;
- class Point{
- int x,y;
- }
- class Edge{
- double l;
- int x,y;
- }
- class KTree{
- int parent,rank;
- }
- public class Kruskal {
- //static Edge e;
- static Edge[] E;
- static Point[] P;
- static KTree[] T;
- static int length;
- public static void union(int a,int b){
- int c;
- if (T[a].rank > T[b].rank){
- c = a;
- a = b;
- b = c;
- }
- else if (T[a].rank != T[b].rank){
- T[a].parent = b;
- }
- else if (T[a].rank == T[b].rank) {
- T[b].rank++;
- }
- T[a].parent = b;
- }
- public static int find(int a){
- if (a == T[a].parent) {
- return a;
- }
- return T[a].parent = find(T[a].parent);
- }
- public static void heapify(int a) {
- int i;
- i = a;
- Edge c;
- if (2*a<length) {
- if (E[a].l>E[2*a].l) {
- i=2*a;
- }
- }
- if (2*a+1<length) {
- if (E[i].l>E[a*2+1].l) {
- i=2*a+1;
- }
- }
- if (i>a) {
- c=E[i];
- E[i]=E[a];
- E[a]=c;
- a=i;
- heapify(a);
- }
- // System.out.println("!!!");
- }
- public static void delete(){
- E[0]=E[length-1];
- length--;
- heapify(0);
- // System.out.println("!");
- }
- public static double SpanningTree(int n){
- int i,k;
- double sum=0.0;
- for (i=length/2; i>=0; i--) {
- heapify(i);
- }
- // System.out.println("!!");
- for (k=0;k!=n-1;) {
- if (find(E[0].x)!=find(E[0].y)) {
- union(find(E[0].x),find(E[0].y));
- sum += E[0].l;
- k++;
- }
- delete();
- }
- return sum;
- }
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int n = in.nextInt();
- int i,j;
- //Edge e=new Edge();
- P = new Point[n];
- E = new Edge[(n*n-n)/2];
- T = new KTree[n];
- length=(n*n-n)/2;
- int k=0;
- double sumMin;
- for (i=0;i<n;i++) {
- T[i]=new KTree();
- P[i]=new Point();
- T[i].parent = i;
- P[i].x=in.nextInt() ;
- P[i].y=in.nextInt() ;
- for (j=i-1;j>=0;j--) {
- Edge e=new Edge();
- e.l = Math.sqrt(((double)(P[i].x-P[j].x)*(P[i].x-P[j].x)+(P[i].y-P[j].y)*(P[i].y-P[j].y)));
- e.x=j;
- e.y=i;
- E[k] = e;
- k++;
- }
- }
- sumMin=SpanningTree(n);
- System.out.printf("%.2f",sumMin);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement