Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Note that there are several ways to build a minimum spanning tree. The method I will use here is called Kruskal's algorithm.
- 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.
- 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.
- 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.
- import java.util.*;
- import java.math.*;
- import java.io.*;
- public class Main {
- static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
- static StringTokenizer st;
- static int nextInt() throws IOException {
- return Integer.parseInt(next());
- }
- static String next() throws IOException {
- while (st == null || !st.hasMoreTokens()) {
- st = new StringTokenizer(in.readLine().trim());
- }
- return st.nextToken();
- }
- public static Path[] paths;
- public static int[] ids;
- public static void main(String[] args) throws IOException {
- int nNodes = nextInt();
- int nPaths = nextInt();
- paths = new Path[nPaths];
- ids = new int[nNodes];
- for (int i = 0; i < nPaths; i++) {
- paths[i] = new Path(nextInt(), nextInt(), nextInt());
- }
- Arrays.sort(paths);
- for (int i = 0; i < nNodes; i++) {
- ids[i] = i;
- }
- System.out.println(doMST());
- }
- // 0 for no mst
- private static long doMST() {
- long bal = 0;
- for (int i = 0; i < paths.length; i++) {
- Path p = paths[i];
- if (ids[p.iS] != ids[p.iE]) {
- bal += p.cost;
- int sColor = ids[p.iS];
- int cColor = ids[p.iE];
- for (int j = 0; j < ids.length; j++) {
- if (ids[j] == cColor) {
- ids[j] = sColor;
- }
- }
- }
- }
- int a = ids[0];
- for (int i = 0; i < ids.length; i++) {
- if (ids[i] != a) {
- return 0;
- }
- }
- return bal;
- }
- }
- class Path implements Comparable<Path> {
- public int iS;
- public int iE;
- public int cost;
- public Path(int u, int v, int cost) {
- iS = u - 1;
- iE = v - 1;
- this.cost = cost;
- }
- @Override
- public int compareTo(Path p) {
- return cost - p.cost;
- }
- @Override
- public String toString() {
- return iS + " " + iE + " " + cost;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement