hdu-2063-过山车(二分图匹配)

Problem Description
RPG girls今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做partner和她同坐。但是，每个女孩都有各自的想法，举个例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题，boss刘决定只让找到partner的人去坐过山车，其他的人，嘿嘿，就站在下面看着吧。聪明的Acmer，你可以帮忙算算最多有多少对组合可以坐上过山车吗？

Input
输入数据的第一行是三个整数K , M , N，分别表示可能的组合数目，女生的人数，男生的人数。0 < K <= 1000 , 1 <= N和M <= 500.
接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。

Output
对于每组数据，输出一个整数，表示可以坐上过山车的最多组合数。

Sample Input
6 3 3
1 1
1 2
1 3
2 1
2 3
3 1
0

Sample Output
3

Author
PrincessSnow

AC Code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace HDU2063 {
    class Program {
        static int[,] map = new int[505, 505];//存放图
        static int[] flag = new int[1005];//标记是否被匹配
        static int[] ok = new int[1005];//标记第i个女生被哪个男生匹配
        static int a, b;
        static bool find(int x) {//用来检测第x个男生是否能匹配到女生
            for (int i = 1; i <= b; i++) {
                if (map[x, i] == 1 && flag[i] == 0) {
                    flag[i] = 1;//标记这个女生已经被匹配
                    if (ok[i] == 0) {//当前没人匹配
                        ok[i] = x;
                        return true;
                    } else {
                        if (find(ok[i])) {//如果前一个可以让出来的话
                            ok[i] = x;//把这个给x
                            return true;
                        }
                    }
                }
            }
            return false;
        }
        static void Main(string[] args) {
            string s;
            while ((s = Console.ReadLine()) != null) {
                string[] ss = s.Split();
                if (ss.Length == 1) break;//只输入一个0 break
                int n = int.Parse(ss[0]); a = int.Parse(ss[1]); b = int.Parse(ss[2]);
                Array.Clear(map, 0, map.Length);
                Array.Clear(ok, 0, ok.Length);
                for (int i = 1; i <= n; i++) {
                    string[] str = Console.ReadLine().Split();
                    int x = int.Parse(str[0]), y = int.Parse(str[1]);
                    map[x, y] = 1;//表示第x个男生可以匹配第y个女生
                }
                int count = 0;
                for (int i = 1; i <= a; i++) {//男生从头到尾扫一遍
                    Array.Clear(flag, 0, flag.Length);
                    if (find(i)) count++;
                }
                Console.WriteLine(count);
            }
        }
    }
}