Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package net.mrpaul.XA270.greedy;
- import java.io.*;
- import java.util.*;
- public class Kruskals {
- private static final Comparator<List<Integer>> C = new Comparator<List<Integer>>() {
- public int compare(List<Integer> pList1, List<Integer> pList2) {
- return pList1.get(0).compareTo(pList2.get(0));
- }
- };
- public static void main(String args[]) throws IOException {
- kruskals("in.txt");
- }
- public static void kruskals(String fileName) throws IOException {
- Scanner scan = new Scanner(new File(fileName));
- int n = Integer.parseInt(scan.nextLine());
- StringTokenizer tokenizer;
- List<List<Integer>> Q = new ArrayList<List<Integer>>();
- List<List<Integer>> E = new ArrayList<List<Integer>>();
- int token;
- List<Integer> e;
- for (int i=0; i<n; i++) {
- Q.add(new ArrayList<Integer>());
- tokenizer = new StringTokenizer(scan.nextLine());
- for (int j=0; j<n; j++) {
- token = Integer.parseInt(tokenizer.nextToken());
- Q.get(i).add(token);
- if (token != -1) {
- e = new ArrayList<Integer>();
- e.add(token);
- e.add(i);
- e.add(j);
- E.add(e);
- }
- }
- }
- Collections.sort(E, C);
- UF U = new UF(n);
- List<List<Integer>> O = new ArrayList<List<Integer>>();
- for (int i=0; i<n; i++) {
- O.add(new ArrayList<Integer>());
- for (int j=0; j<n; j++) {
- O.get(i).add(-1);
- }
- }
- int s;
- int f;
- int sum = 0;
- while (U.count() > 1) {
- e = E.get(0);
- E.remove(0);
- s = e.get(1);
- f = e.get(2);
- if (!U.connected(s, f)) {
- U.union(s, f);
- O.get(s).set(f, e.get(0));
- O.get(f).set(s, e.get(0));
- sum += e.get(0);
- }
- }
- String o = "";
- for (int i=0; i<n; i++) {
- for (int j=0; j<n; j++) {
- o += O.get(i).get(j)+" ";
- }
- o += "\n";
- }
- o += sum;
- BufferedWriter out = new BufferedWriter(new FileWriter("out.txt"));
- out.write(o);
- out.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement