4237205_ac_735ms_10028k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main {
	private Scanner in;
	
	private int m, n;

	private int[][] map = new int[1000][501];

	private int[][] link = new int[500][];

	private boolean[] b = new boolean[500];

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

	private void run() {
		in = new Scanner(System.in);

		while (true) {
			n = in.nextInt();
			m = in.nextInt();

			if (n == 0) {
				break;
			}
			in.nextLine();
			for (int i = 0; i < n; i++) {
				String line = in.nextLine();
				StringTokenizer st = new StringTokenizer(line, " \n");
				st.nextToken();
				map[i][0] = 0;
				while (st.hasMoreTokens()) {
					map[i][++map[i][0]] = Integer.parseInt(st.nextToken());
				}
			}
			solve();
		}
	}

	private void solve() {
		int mid, min, max;

		min = n / m;
		max = n;

		while (min < max) {
			mid = (min + max) >> 1;
			if (match(mid)) {
				max = mid;
			} else {
				min = mid + 1;
			}
		}
		System.out.println(min);
	}

	private boolean match(int cap) {
		for (int i = 0; i < m; i++) {
			link[i] = new int[cap + 1];
		}
		for (int i = 0; i < n; i++) {
			Arrays.fill(b, false);
			if (!find(i)) {
				return false;
			}
		}
		return true;
	}

	private boolean find(int u) {
		for (int i = 1; i <= map[u][0]; i++) {
			int v = map[u][i];
			if (!b[v]) {
				b[v] = true;
				if (link[v][0] < link[0].length - 1) {
					link[v][++link[v][0]] = u;
					return true;
				}
				for (int j = 1; j < link[0].length; j++) {
					if (find(link[v][j])) {
						link[v][j] = u;
						return true;
					}
				}
			}
		}
		return false;
	}
}