Advertisement
Guest User

Untitled

a guest
Jan 21st, 2020
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.02 KB | None | 0 0
  1. Note that there are several ways to build a minimum spanning tree. The method I will use here is called Kruskal's algorithm.
  2.  
  3. Kruskal's algorithm is a greedy algorithm, meaning that we will always try the best possible case. It is recommended that you declare a class that implements Comparable<> to store each edge.
  4.  
  5. Store the edges in an array and sort it by cost. Then, preprocess a disjoint set union algorithm on the array. Iterate over the array and for each path that connects two nodes which do not have a union, connect it via DSU and increase the cost. The problem constraints make it so that naive DSU will pass.
  6.  
  7. Once you reach the end of the array, return the total cost. An implementation of the algorithm in java is shown here. Converting this into processing should be a trivial task.
  8.  
  9. import java.util.*;
  10. import java.math.*;
  11. import java.io.*;
  12.  
  13. public class Main {
  14.    
  15.     static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  16.     static StringTokenizer st;
  17.  
  18.     static int nextInt() throws IOException {
  19.         return Integer.parseInt(next());
  20.     }
  21.  
  22.     static String next() throws IOException {
  23.         while (st == null || !st.hasMoreTokens()) {
  24.             st = new StringTokenizer(in.readLine().trim());
  25.         }
  26.         return st.nextToken();
  27.     }
  28.    
  29.     public static Path[] paths;
  30.     public static int[] ids;
  31.  
  32.     public static void main(String[] args) throws IOException {
  33.        
  34.         int nNodes = nextInt();
  35.         int nPaths = nextInt();
  36.  
  37.         paths = new Path[nPaths];
  38.         ids = new int[nNodes];
  39.  
  40.         for (int i = 0; i < nPaths; i++) {
  41.  
  42.             paths[i] = new Path(nextInt(), nextInt(), nextInt());
  43.  
  44.         }
  45.  
  46.         Arrays.sort(paths);
  47.  
  48.         for (int i = 0; i < nNodes; i++) {
  49.  
  50.             ids[i] = i;
  51.  
  52.         }
  53.  
  54.         System.out.println(doMST());
  55.  
  56.     }
  57.  
  58.     // 0 for no mst
  59.     private static long doMST() {
  60.  
  61.         long bal = 0;
  62.  
  63.         for (int i = 0; i < paths.length; i++) {
  64.  
  65.             Path p = paths[i];
  66.  
  67.             if (ids[p.iS] != ids[p.iE]) {
  68.  
  69.                 bal += p.cost;
  70.  
  71.                 int sColor = ids[p.iS];
  72.                 int cColor = ids[p.iE];
  73.                 for (int j = 0; j < ids.length; j++) {
  74.  
  75.                     if (ids[j] == cColor) {
  76.  
  77.                         ids[j] = sColor;
  78.  
  79.                     }
  80.  
  81.                 }
  82.  
  83.             }
  84.  
  85.         }
  86.  
  87.         int a = ids[0];
  88.  
  89.         for (int i = 0; i < ids.length; i++) {
  90.  
  91.             if (ids[i] != a) {
  92.  
  93.                 return 0;
  94.  
  95.             }
  96.  
  97.         }
  98.  
  99.         return bal;
  100.     }
  101. }
  102.  
  103. class Path implements Comparable<Path> {
  104.  
  105.     public int iS;
  106.     public int iE;
  107.     public int cost;
  108.  
  109.     public Path(int u, int v, int cost) {
  110.  
  111.         iS = u - 1;
  112.         iE = v - 1;
  113.         this.cost = cost;
  114.  
  115.     }
  116.  
  117.     @Override
  118.     public int compareTo(Path p) {
  119.  
  120.         return cost - p.cost;
  121.  
  122.     }
  123.  
  124.     @Override
  125.     public String toString() {
  126.  
  127.         return iS + " " + iE + " " + cost;
  128.  
  129.     }
  130.  
  131. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement