girlsandboys.java

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

package PKU.Hungary;
import java.util.*;


/**
 * ID:1466
 * 匈牙利算法
 * K?0?2nig定理:一个二分图中的最大匹配数等于这个图中的最小点覆盖数(最少几个点可以覆盖全部边)
 * @author yhm
 *
 */
public class GirlsandBoys {

	static int RIGHT_MAX=501;
	static int LEFT_MAX=501;
	
	static boolean[] useif =new boolean[RIGHT_MAX];
	
	//link[]记录与右边元素连接的元素，-1表示没有连接
	static int[] link = new int[RIGHT_MAX];

	static int left_num,right_num;

	static boolean array[][] = new boolean[LEFT_MAX][RIGHT_MAX];
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int i,k,num,temp,num_of_this;
	    Scanner cin = new Scanner(System.in);
		while(cin.hasNext())
	    {
			left_num = cin.nextInt();
	        right_num=left_num;
			//link??-1

			for(int j=0;j<left_num;j++){
				Arrays.fill(array[j], false);
			}
			Arrays.fill(link, -1);
			
			
			num=0;
			
			for(i=0;i<left_num;i++)
			{
				cin.next();
				String str = cin.next();
				str = str.substring(1, str.length()-1);
				num_of_this = Integer.parseInt(str);
				for(k=0;k<num_of_this;k++)
				{
					temp = cin.nextInt();
					array[i][temp]=true;
				}
			}
			

			
			//匹配，num为结果
			for(i=0;i<left_num;i++)
			{
				Arrays.fill(useif, false);
				if(can(i))
					num++;
			}

		
			System.out.println(left_num-num/2);
			
		}

	}



	
	static boolean can(int t)
	{
		int i;
		
		for(i=0;i<right_num;i++)
		{
			if(!useif[i]&&array[t][i])
			{
				useif[i]=true;
				if(link[i]==-1||can(link[i]))
				{
					link[i]=t;
					return true;
				}
			}

		}
		return false;
	}
	
}