pal2

gistfile1.java

package pal;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;

public class Main {
//	public Link[] usedLinks;
	public long[] linkks;
	public int usedLinksPointer=0;
	public HashMap<Integer, Link> hmil=null; 
	int hCount, rootCount; // house count
	int lines; // internet lines count
	Node[] nodes; // nodes = hCount

	static boolean local = true;

	public static void main(String[] args) throws Exception {
		if (args.length != 0) {
			local = true;
		} else {
			local = false;
		}
//		 Thread.sleep(10000);
		Main task = new Main();
		task.initData();
		task.disJoin();

		Results.buildings = new StringBuffer();
		int houseCount = 0;
		for (int i = 1; i < task.nodes.length; i++) {
			if (!task.nodes[i].child) {
				houseCount++;
				Results.buildings.append(i);
				Results.buildings.append(" ");
			}
		}
		if (houseCount > task.lines) {
			System.out.println("-1");
			return;
		} 
		
		System.out.println(Results.sum);
		System.out.println(Results.buildings.toString().trim());
		System.out.println(Results.links.append(Results.zeros));
	}

	
	
	private void initData() throws Exception {
		
		BufferedReader br = null;
		if (local == true)
			br = new BufferedReader(new FileReader("./test3.in"));
		else
			br = new BufferedReader(new InputStreamReader(System.in));

		hCount = Integer.parseInt(br.readLine());
		lines = Integer.parseInt(br.readLine());

		nodes = new Node[hCount + 1];

		for (int i = 0; i < hCount + 1; i++) {
			nodes[i] = new Node();
		}
		
		linkks = new long[6000000];
		
		int linkPointer = 0;
		int nodeA, nodeB, price;
		int[] nums = lineToNums(br.readLine().toCharArray());
		while (true) {
			nodeA = nums[0];
			nodeB = nums[1];
			price = nums[2];

			if (nodeA == 0 && nodeB == 0 && price == 0)
				break;

			if (nodeA > nodeB) {
				int tmp = nodeA;
				nodeA = nodeB;
				nodeB = tmp;
			}
			
			linkks[linkPointer]=setNodeB(linkks[linkPointer],nodeB);
			linkks[linkPointer]=setNodeA(linkks[linkPointer],nodeA);
			linkks[linkPointer]=setPrice(linkks[linkPointer],price);
			linkPointer++;

			nums = lineToNums(br.readLine().toCharArray());
		}
		linkPointer--;
		
		
		Arrays.sort(linkks, 0, linkPointer);
		for(int i=0; i<linkPointer-1;i++){
			if(getNodeA(linkks[linkPointer])==getNodeA(linkks[linkPointer+1])&&
					getNodeB(linkks[linkPointer])==getNodeB(linkks[linkPointer+1])){
//				setPrice(linkks[linkPointer+1],100000);
				setPrice(linkks[linkPointer+1],65535);
//				linkks[linkPointer+1]=0;
			}
		}
		Arrays.sort(linkks, 0, linkPointer);
		linkks = Arrays.copyOfRange(linkks, 0, linkPointer);

	}

	static private long setNodeB(long l, int i){
		return l |= i; 
	}

	static private long setNodeA(long l, int i){
		i<<=16;
		return l |= i; 
	}
	static private long setPrice(long l, int i){
		long tmp = i;
		tmp<<=32;
		return l |= tmp; 
	}
	
	
	static private int getNodeB(long l){
		return (int)(l&0x0FFFFL);
	}
	static private int getNodeA(long l){
		l=l&0x0FFFF0000L;
		l>>=16;
		return (int)l;
	}
	static private int getPrice(long l){
		l=l&0x0FFFF00000000L;
		l>>=32;
		return (int)l;
	}
	static private long setUsed(long l){
		l|=0x1000000000000L;
		return l;
		
	}
	
	private void disJoin() {
		Results.links = new StringBuffer();
		Results.sum = 0;
		rootCount=0;
		for (int i = 0; i < linkks.length; i++) {
			long current = linkks[i];
			if(getPrice(current)==123456) continue;
			Node a = nodes[getNodeA(current)];
			Node b = nodes[getNodeB(current)];
			Node parentA = find_set(a);
			Node parentB = find_set(b);
			if (parentA != parentB) {
				rootCount--; // count of root nodes
				setUsed(current); // mark used links
				union(a, b, parentA, parentB);

				Results.sum+=getPrice(current);
				Results.links.append(getNodeA(current));
				Results.links.append(" ");
				Results.links.append(getNodeB(current));
				Results.links.append(" ");
				Results.links.append(getPrice(current));
				Results.links.append("\n");
			}
			if((hCount+rootCount)==lines)break;
		}
	
	}

	static private void union(Node a, Node b, Node parentA, Node parentB) {
//		Node aRoot = parentA;
//		Node bRoot = parentB;
		Node aRoot = find_set(a);
		Node bRoot = find_set(b);
		if (aRoot.rank > bRoot.rank) {
			bRoot.parent = aRoot;
			bRoot.child = true;
			aRoot.child = false;
			return;
		} else if (aRoot != bRoot) {
			aRoot.parent = bRoot;
			if (aRoot.rank == bRoot.rank) {
				bRoot.rank++;
			}
			bRoot.child = false;
			aRoot.child = true;
			return;
		}
	}

	static private Node find_set(Node a) {
		if (a.parent == a)
			return a;
		else
			return find_set(a.parent);
	}

	static private int[] lineToNums(char[] input) {
		char[] line = input;
		int[] output = new int[3];
		int outputIndex = 2;
		int num = 0;
		int base = 0;
		int exponent = 1;
		for (int i = line.length - 1; i >= 0; i--) {
			switch (line[i]) {
			case '1':
				base = 1;
				break;
			case '2':
				base = 2;
				break;
			case '3':
				base = 3;
				break;
			case '4':
				base = 4;
				break;
			case '5':
				base = 5;
				break;
			case '6':
				base = 6;
				break;
			case '7':
				base = 7;
				break;
			case '8':
				base = 8;
				break;
			case '9':
				base = 9;
				break;
			case '0':
				base = 0;
				break;
			case ' ':
				output[outputIndex] = num;
				exponent = 1;
				outputIndex--;
				num = 0;
				continue;
			}
			num += exponent * base;
			exponent *= 10;
		}
		output[outputIndex] = num;
		return output;
	}

	class Node {
		public int rank;
		public Node parent = null;
		public boolean child = false;

		public Node() {
			parent = this;
			rank = 0;
		}

	}

	class Link {
		public int nodeA, nodeB;
		public int price;
		public boolean used = false;

		public Link(int a, int b, int price) {
			nodeA = a;
			nodeB = b;
			this.price = price;
		}
	}

	class Comp_price implements Comparator<Link> {
		@Override
		public int compare(Link o1, Link o2) {
			if (o1.price < o2.price) {
				return -1;
			} else if (o1.price > o2.price) {
				return 1;
			} else {
				if (o1.nodeA < o2.nodeA) {
					return -1;
				} else if (o1.nodeA > o2.nodeA) {
					return 1;
				} else {
					if (o1.nodeB < o2.nodeB) {
						return -1;
					} else if (o1.nodeB > o2.nodeB) {
						return 1;
					} else {
						return 0;
					}
				}
			}
		}
	}

	static class Results {
		public static int sum = 0;
		public static StringBuffer buildings = null;
		public static StringBuffer links = null;
		public static String zeros = "0 0 0";
		public static String error = "-1";
	}

}