asteroids.java

PKU中一些数据结构基本算法题的java实现

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


/**
 * ID:3041
 * 匈牙利算法 
 * K?0?2nig定理:一个二分图中的最大匹配数等于这个图中的最小点覆盖数(最少几个点可以覆盖全部边)
 * @author yhm
 *
 */
public class Asteroids {
	static boolean[][] array;
	static boolean[] use;
	static int[] link;
	static int size;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			size = cin.nextInt();
			int M = cin.nextInt();
			
			array = new boolean[size][size];
			use = new boolean[size];
			link = new int[size];
			for(int j=0;j<size;j++){
				Arrays.fill(array[j], false);
			}
			Arrays.fill(link, -1);
			
			for(int i=0;i<M;i++){
				int x=cin.nextInt()-1;
				int y=cin.nextInt()-1;
				array[x][y] = 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;
	}

}