import java.io.*;
import java.util.*;

class GirlsAndBoys {
	static int num_student, num_match;
	static int[][] relation;
	static int[] gender, mate;
	static boolean[] visited;

	static boolean loadRelationship(BufferedReader input) throws IOException {
		String line = input.readLine();
		if ( line==null || line.length()==0 )
			return false;
		num_student = Integer.parseInt(line);
		relation = new int[num_student][];
		for ( int i=0; i<num_student; i++ ) { // load into adjacency list
			StringTokenizer tokens = new StringTokenizer(input.readLine(), " :()");
			int id = Integer.parseInt(tokens.nextToken());
			int num = Integer.parseInt(tokens.nextToken());
			relation[id] = new int[num];
			for ( int j=0; j<num; j++ )
				relation[id][j] = Integer.parseInt(tokens.nextToken());
		}
		return true;
	}

	static void labelGender() {
		LinkedList<Integer> queue = new LinkedList<Integer>();
		for ( int s=0; s<num_student; s++ )
			if ( gender[s] == 0 ) { // if not assigned
				gender[s] = 1;	// set to boy
				queue.add(new Integer(s));
				while ( ! queue.isEmpty() ) {
					int t = queue.remove(0).intValue();
					for ( int i=0; i<relation[t].length; i++ )
						if ( gender[relation[t][i]] == 0 ) {
							gender[relation[t][i]] = - gender[t];
							queue.add(new Integer(relation[t][i]));
						}
				}
			}
	}

	static boolean findPath(int start) {
		for ( int i=0; i<relation[start].length; i++ )
			if ( ! visited[relation[start][i]] ) {
				visited[relation[start][i]] = true;
				int next = mate[relation[start][i]];
				if ( next==-1 || findPath(next) ) {
					mate[relation[start][i]] = start;
					mate[start] = relation[start][i];
					return true;
				}
			}
		return false;
	}

	static void hungarianMatch() {
		for ( int s=0; s<num_student; s++ )
			if ( gender[s]==-1 && mate[s]==-1 ) { // only start from unmatched girl
				Arrays.fill(visited, false);
				if ( findPath(s) )
					num_match ++;
			}
	}

	public static void main (String[] args) throws IOException {
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		while ( loadRelationship(input) ) {
			num_match = 0;
			gender = new int[num_student];
			visited = new boolean[num_student];
			mate = new int[num_student];
			Arrays.fill(mate, -1);
			labelGender();
			hungarianMatch();
			System.out.println(num_student-num_match);
		}
	}
}

• 又被阴了一把...原来是因为输入数据不同cases之间有空行...原题中没说有呀？ (0) gongml 2005-10-18 19:54:19
  • 我不明白……为什么总有人喜欢想象数据中没有的情况，自己错了就赖数据…… (0) frkstyc 2005-10-18 19:58:21
    • 我不明白……为什么总有人喜欢想象别人和自己一样牛,自己牛了就赖别人…… (0) Sinbad 2005-10-18 20:26:12
      • 呵呵，这个根本就不是牛不牛的问题，怀疑就该从自己开始而不是从数据开始 (0) frkstyc 2005-10-18 20:31:21
        • 就是因为我对匹配不熟，所以一直怀疑自己。如果早一点怀疑数据，n天前就AC了... (595) gongml 2005-10-18 20:41:53
          • 实际上这些完全是可以避免的 (160) frkstyc 2005-10-18 20:54:58
            • 的确如此，花些时间买了个教训。无论如何还要谢谢你一开始指出我的misunderstanding (0) gongml 2005-10-18 21:03:33
            • 当然还要感谢 TEER verify 我的输出。不然，我一定想不到问题所在... (0) gongml 2005-10-18 21:06:29
    • 可是我只改了一处就AC了!还能有其它原因吗？ (0) gongml 2005-10-18 20:30:26
      • changed from "if ( line==null || line.length()==0 ) return false; // no more cases" (0) gongml 2005-10-18 20:31:06
      • to "while ( line.trim().length() == 0 ) line = input.readLine();" (0) gongml 2005-10-18 20:31:36