过山车 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
输入数据的第一行是三个整数K , M , N,分别表示可能的组合数目,女生的人数,男生的人数。1≤K<=1000 1<=N 和M<=500.接下来的K行,每行有两个数,分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。
Output 对于每组数据,输出一个整数,表示可以坐上过山车的最多组合数。
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
题解 匈牙利算法模板
## 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; 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) { 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 ; } }