theperfectstall.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 73 行

package PKU.Hungary;
import java.util.Arrays;
import java.util.Scanner;


/**
 * ID:1274
 * 匈牙利算法
 * @author yhm
 *
 */
public class ThePerfectStall {

	static int N,M;
	static int[] link;
	static boolean[] use;
	static boolean[][] array;
	static int size;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			N = cin.nextInt();
			M = cin.nextInt();
			
			size = N+M;
			array = new boolean[size][size];
			link = new int[size];
			Arrays.fill(link, -1);
			use = new boolean[size];
			
			for(int i=0;i<N;i++){
				int num = cin.nextInt();
				for(int j=0;j<num;j++){
					int col = cin.nextInt();
					array[i][col-1] = true;
				}
			}
			
			int num=0;
			for(int i=0;i<size;i++){
				Arrays.fill(use, false);
				if(can(i)){
					num++;
				}
			}
			
			
			System.out.println(num);
			
		}

	}
	
	static boolean can(int i){
		
		for(int j=0;j<size;j++){
			if(!use[j] && array[i][j]){
				use[j] = true;
				if(link[j]==-1 || can(link[j])){
					link[j] = i;
					return true;
				}
			}
		}
		
		return false;
	}

}