guardianofdecency.java

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

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

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

	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);
		int caseNum = cin.nextInt();
		for (int i = 0; i < caseNum; i++) {
			size = cin.nextInt();
			Person[] persons = new Person[size];
			for (int j = 0; j < size; j++) {
				int height = cin.nextInt();
				String sex = cin.next();
				String music = cin.next();
				String sport = cin.next();
				persons[j] = new Person(height, sex, music, sport);
			}

			buildArray(persons);

			int num = 0;
			for (int j = 0; j < size; j++) {
				Arrays.fill(use, false);
				if (can(j)) {
					num++;
				}
			}
			System.out.println(size-num/2);

		}

	}

	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;
	}

	static void buildArray(Person[] persons) {
		array = new boolean[size][size];
		use = new boolean[size];
		link = new int[size];
		Arrays.fill(link, -1);
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				if (i == j) {
					array[i][j] = false;
				} else {
					if (fallInLove(persons[i], persons[j])) {
						array[i][j] = true;
					} else {
						array[i][j] = false;
					}
				}
			}
		}
	}

	static boolean fallInLove(Person a, Person b) {
		if (Math.abs(a.height - b.height) > 40) {
			return false;
		}
		if (a.sex.equals(b.sex)) {
			return false;
		}
		if (!a.music.equals(b.music)) {
			return false;
		}
		if (a.sport.equals(b.sport)) {
			return false;
		}
		return true;
	}

}

class Person {
	int height;
	String sex;
	String music;
	String sport;

	public Person(int height, String sex, String music, String sport) {
		super();
		this.height = height;
		this.sex = sex;
		this.music = music;
		this.sport = sport;
	}
}