hdu2063过山车

1、匈牙利算法；

2、二分图最大匹配

import java.util.Scanner;

public class Main {

    public static boolean find(int cur, int[] pre, boolean[][] map, boolean[] vis){
        for (int i = 1; i < pre.length; i++) {
            if (map[cur][i] && !vis[i]){
                vis[i] = true;
                if (pre[i]==-1 || find(pre[i],pre,map,vis)){
                    pre[i] = cur;
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int hang = sc.nextInt();
            if (hang==0){
                break;
            }
            int res = 0;
            int girl = sc.nextInt();
            int boy = sc.nextInt();
            /*女找男*/
            int[] pre = new int[boy+1];/*记录男的被谁选择了*/
            boolean[][] map = new boolean[girl+1][boy+1];
            boolean[] vis = new boolean[boy+1];/*临时记录男的是否 被选*/
            for (int i = 1; i <= boy; i++) {
                pre[i] = -1;
            }
            for (int i = 0; i < hang; i++) {
                int aa = sc.nextInt();
                int bb = sc.nextInt();
                map[aa][bb] = true;
            }
            for (int i = 1; i <=girl ; i++) {
                for (int j = 1; j <=boy ; j++) {
                    vis[j] = false;
                }
                if (find(i,pre,map,vis)){
                    res++;
                }
            }
            System.out.println(res);
        }

    }
}