UVA – 1062 – Containers   Leave a comment


Minimum path cover on a dag, I believe it can be also solved using a greedy algorithm.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;

public class UVa1062 {
	boolean[] v;
	int[] pair;
	LinkedList<Integer>[] G;

	public int path(int i) {
		if (v[i])
			return 0;
		v[i] = true;
		for (int j : G[i])
			if (pair[j] == -1 || path(pair[j]) != 0) {
				pair[j] = i;
				return 1;
			}
		return 0;
	}

	public int match() {
		int match = 0;
		Arrays.fill(pair, -1);
		for (int i = 0; i < G.length; i++) {
			Arrays.fill(v, false);
			match += path(i);
		}
		return match;
	}

	public void run() throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		v = new boolean[1005];
		pair = new int[1005];
		int cc = 1;
		while (true) {
			char[] arr = in.readLine().trim().toCharArray();
			if (arr.length == 3 && arr[0] == 'e' && arr[1] == 'n'
					&& arr[2] == 'd')
				return;
			G = new LinkedList[arr.length];
			for (int i = 0; i < G.length; i++) {
				G[i] = new LinkedList<Integer>();
				for (int j = i + 1; j < arr.length; j++)
					if (arr[j] <= arr[i])
						G[i].add(j);

			}
			System.out.printf("Case %d: %d\n", cc++, arr.length - match());
		}
	}

	public static void main(String[] args) throws Exception {
		(new UVa1062()).run();
	}
}

Advertisements

Posted November 15, 2012 by epicrado in DAG, Graphs

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: