2012年4月 春コンテスト Problem B: AYBABTU (貪欲に森を大きく) [Licence: NYSL Version 0.9982]

Main.java

import java.util.*;

public class Main implements Runnable {

  private final V[] bases;
	private final int n, k;

	private Main(V[] bases, int n, int k) {
		this.bases = bases;
		this.n = n;
		this.k = k;
	}

	private static class E implements Comparable<E> {
		private static int nid = 0;
		final int id = nid++;
		final int cost;
		final E rev;
		final V to;
		private boolean used = false;

		public E(V from, V to, int cost) {
			this.cost = cost;
			this.to = to;
			this.rev = new E(this, from);
			from.add(this);
			to.add(this.rev);
		}

		private E(E rev, V to) {
			this.rev = rev;
			this.to = to;
			this.cost = rev.cost;
		}

		@Override
		public int compareTo(E o) {
			final int d = cost - o.cost;
			return d == 0 ? id - o.id : d;
		}
	}

	private static class V extends HashSet<E> {
		private static int nid = 0;
		public final int id = nid++;
	}

	private static int caseNum = 1;

	@Override
	public void run() {
		final UnionFind uf = new UnionFind();
		final NavigableSet<E> set = new TreeSet<E>();
		for (final V v : bases) {
			uf.union(bases[0], v);
			for (final E e : v)
				if (!e.used) {
					set.add(e);
					e.used = e.rev.used = true;
				}
		}
		int ans = 0;
		for (int r = bases.length - 1 - k; r > 0;) {
			final E ee = set.pollLast();
			if (!uf.union(ee.to, ee.rev.to))
				r--;
			for (final E e : ee.to)
				if (!e.used) {
					set.add(e);
					e.used = e.rev.used = true;
				}
		}
		while (!set.isEmpty()) {
			final E ee = set.pollLast();
			if (!uf.union(ee.to, ee.rev.to))
				ans += ee.cost;
			for (final E e : ee.to)
				if (!e.used) {
					set.add(e);
					e.used = e.rev.used = true;
				}
		}
		System.out.println("Case " + (caseNum++) + ": " + ans);
	}

	private class UnionFind {
		private final int[] tree;

		public UnionFind() {
			tree = new int[n];
			Arrays.fill(tree, -1);
		}

		public int root(final int x) {
			return tree[x] < 0 ? x : (tree[x] = root(tree[x]));
		}

		public boolean union(V vx, V vy) {
			int x = root(vx.id);
			int y = root(vy.id);
			if (x == y)
				return false;
			if (tree[x] > tree[y]) {
				final int t = x;
				x = y;
				y = t;
			}
			tree[x] += tree[y];
			tree[y] = x;
			return true;
		}
	}

	public static void main(String... args) {
		final Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			System.gc();
			if(!solve(sc))
				break;
		}
	}

	public static boolean solve(Scanner sc) {
		final int n = sc.nextInt();
		final int t = sc.nextInt();
		final int k = sc.nextInt();
		if (n == 0 && t == 0 && k == 0)
			return false;
		V.nid = 0;
		final V[] vs = new V[n];
		for (int i = 0; i < n; i++)
			vs[i] = new V();
		for (int i = 1; i < n; i++) {
			final int l = sc.nextInt() - 1;
			final int r = sc.nextInt() - 1;
			final int c = sc.nextInt();
			new E(vs[l], vs[r], c);
		}
		V[] bases = new V[t];
		for (int i = 0; i < t; i++)
			bases[i] = vs[sc.nextInt() - 1];
		new Main(bases, n, k).run();
		return true;
	}

	public static void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}