2012年4月 春コンテスト Problem B: AYBABTU (貪欲に切断) [Licence: NYSL Version 0.9982]

Main.java

import java.util.*;

public class Main implements Runnable {

  private final V s;
	private final int k;

	private Main(V s, int k) {
		this.s = s;
		this.k = k;
	}

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

		public E(V from, V to, int cost) {
			this.to = to;
			this.cost = cost;
			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> {
		boolean isBase = false;
		V v = null;
		int min = Integer.MAX_VALUE;
	}

	@Override
	public void run() {
		NavigableSet<E> es = contract();
		int ans = 0;
		for (int i = 0; i < k; i++) {
			final E e = es.pollFirst();
			//debug(e.cost);
			ans += e.cost;
			remove(es, e);
			remove(es, e.rev);
		}
		System.out.println(ans);
	}

	private NavigableSet<E> contract() {
		final NavigableSet<E> es = new TreeSet<E>();
		final Deque<V> st = new ArrayDeque<V>();
		st.offerFirst(s);
		while (!st.isEmpty()) {
			final V v = st.pollFirst();
			if (v.v == null) {
				v.v = new V();
				v.v.isBase = v.isBase;
			}
			if (v.isEmpty()) {
				if ((!v.v.isEmpty() || v.v.isBase) && !st.isEmpty())
					es.add(new E(v.v, st.peekFirst().v, v.min));
			} else {
				final E e = v.iterator().next();
				v.remove(e);
				e.to.min = e.cost;
				e.to.remove(e.rev);
				st.offerFirst(v);
				st.offerFirst(e.to);
			}
		}
		return es;
	}

	private void remove(final NavigableSet<E> es, E e) {
		while (true) {
			es.remove(e);
			es.remove(e.rev);
			e.to.remove(e.rev);
			if (e.to.isBase || e.to.size() > 1)
				break;
			e.to.remove(e = e.to.iterator().next());
		}
	}

	public static void main(String... args) {
		final Scanner sc = new Scanner(System.in);
		for (int T = 1; sc.hasNext(); T++) {
			System.gc();
			if(!solve(sc, T))
				break;
		}
	}

	public static boolean solve(Scanner sc, int T) {
		final int n = sc.nextInt();
		final int t = sc.nextInt();
		final int k = sc.nextInt();
		if(n == 0 && t == 0 && k == 0)
			return false;
		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 s = null;
		for (int i = 0; i < t; i++) {
			final int b = sc.nextInt() - 1;
			vs[b].isBase = true;
			s = vs[b];
		}
		System.out.printf("Case %d: ", T);
		new Main(s, k).run();
		return true;
	}

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