Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- class Vertex{
- int x;
- int y;
- int depth;
- Vertex parent;
- public Vertex (int x, int y) {
- this.x = x;
- this.y = y;
- depth = 0;
- parent = this;
- }
- }
- //class Length implements Comparable<Length> {
- class Length{
- Vertex u;
- Vertex v;
- double len;
- Length(Vertex u, Vertex v, double len) {
- this.len = len;
- this.u = u;
- this.v = v;
- }
- public static Vertex Find(Vertex x) {
- if (x.parent == x)
- return x;
- return Find(x.parent);
- }
- public static void Union(Vertex x, Vertex y) {
- Vertex rootX = Length.Find(x);
- Vertex rootY = Length.Find(y);
- if (rootX.depth < rootY.depth)
- rootX.parent = rootY;
- else {
- rootY.parent = rootX;
- if (rootX.depth == rootY.depth && rootX != rootY)
- rootX.depth++;
- }
- }
- }
- public class Kruskal {
- /*public static Vertex ExtractMin( PriorityQueue<Length> q) {
- Vertex ptr = q.heap[0];
- if (ptr.x == 0)
- System.out.println("panic");
- q.count--;
- if(q.count > 0) {
- q.heap[0] = q.heap[q.count];
- q.heap[0].index = 0;
- //Heapify(0,q.count,q.heap);
- }
- return ptr;
- }
- */
- public double SpanningTree(PriorityQueue<Length> q) {
- double E = 0;
- for (Length i : q) {
- if (Length.Find(i.u) != Length.Find(i.v)) {
- E = E + i.len;
- Length.Union(i.u, i.v);
- }
- }
- return E;
- }
- public double MST_Kruskal(PriorityQueue<Length> q) {
- //ExtractMin(q);
- return SpanningTree(q);
- }
- public static int N;
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int x, y;
- N = in.nextInt();
- Vertex[] g = new Vertex[N];
- PriorityQueue<Length> q = new PriorityQueue<>(1000);
- for ( int i = 0; i < N; i++) {
- x = in.nextInt();
- y = in.nextInt();
- g[i] = new Vertex(x,y);
- }
- for ( int i = 0; i < N; i++) {
- for (int j = i + 1; j < N; j++) {
- double length = Math.sqrt((g[i].x - g[j].x)*(g[i].x - g[j].x) + (g[i].y - g[j].y)*(g[i].y - g[j].y));
- q.add(new Length(g[i], g[j], length));
- //g[i].lists.add(j);
- }
- }
- Kruskal k = new Kruskal();
- double a = k.MST_Kruskal(q);
- System.out.printf("%.2f",a);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement