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

传送门:HDU2063

Input

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

Output

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

Sample Input

1
2
3
4
5
6
7
8
6 3 3
1 1
1 2
1 3
2 1
2 3
3 1
0

Sample Output

1
3

题解

匈牙利算法模板
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.io.*;  
import java.util.*;
public class Main {

public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
while(sc.hasNext()){
int k=sc.nextInt();
if(k==0)break;
int m=sc.nextInt();
int n=sc.nextInt();
BGraph bg=new BGraph(n,m);
for(int i=0;i<k;i++){
int a=sc.nextInt();
int b=sc.nextInt();
bg.line[b][a]=true;
}
int count=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){ /*每次都要初始化 重要!*/
bg.used[j]=false;
}
if(bg.find(i))count++;
}
pw.println(count);
pw.flush();
}
}
}
class BGraph{
int m;//妹子的人数
boolean[][] line;//男女关系
boolean[]used;//m
int[]girl;//妹子的归属
BGraph(int n,int m){
line=new boolean[n+1][m+1];
used=new boolean[m+1];
girl=new int[m+1];
this.m=m;
}
boolean find(int x){ //x是男,找妹子
int i,j;

for (j=1;j<=m;j++){ //扫描每个妹子
if (line[x][j]==true && used[j]==false)
//如果有暧昧并且还没有标记过(这里标记的意思是这次查找曾试图改变过该妹子的归属问题,但是没有成功,所以就不用瞎费工夫了)
{
used[j]=true;
if (girl[j]==0 || find(girl[j])) {
//名花无主或者能腾出个位置来,这里使用递归
girl[j]=x;
return true;
}
}
}
return false;
}
}