HDU 2063ジェットコースター二分法ハンガリー裸題


B-ジェットコースター
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit 
Status
Description
RPG girlsは今日、みんなで遊園地に遊びに行って、やっと夢のジェットコースターに乗ることができました.しかし、ジェットコースターの各列には2つの席しかありません.そして、女の子一人一人が男の子を探してパートナーをして彼女と一緒に座らなければなりません.しかし、女の子はそれぞれの考えを持っていて、例えば、RabbitはXHDやPQKとパートナーをしたいだけで、GrassはlinleやLLとパートナーをしたいだけで、PrincesssSnowは水域の波や偽クールとパートナーをしたいと思っています.経費の問題を考慮して、boss劉はパートナーを見つけた人だけをジェットコースターに乗らせることにした.他の人は、へへ、下に立って見ていただろう.賢いAcmer、ジェットコースターに乗れる組み合わせはどれくらいあるか計算してもらえますか?
 
Input
入力データの最初の行は3つの整数K,M,Nであり,それぞれ可能な組合せ数,女子の人数,男子の人数を表す.01<=NおよびM<=500である.次のK行は、行ごとに2つの数があり、それぞれ女子Aiが男子Bjとパートナーをしたいことを示しています.最後の0は入力を終了します.
 
Output
各グループのデータについて、ジェットコースターに乗れる最大の組み合わせ数を示す整数を出力します.
 
Sample Input

        
        
        
        
6 3 3 1 1 1 2 1 3 2 1 2 3 3 1 0

 
Sample Output

        
        
        
        
3

 
ACcode:
#pragma warning(disable:4786)//         
#pragma comment(linker, "/STACK:102400000,102400000")//    
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rds(x) scanf("%s",x)
#define rdc(x) scanf("%c",&x)
#define ll long long int
#define maxn 505
#define mod 1000000007
#define INF 0x3f3f3f3f //int    
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i)
#define MT(x,i) memset(x,i,sizeof(x))
#define PI  acos(-1.0)
#define E  exp(1)
using namespace std;
bool bmap[maxn][maxn];
bool bmask[maxn];
int nx,ny;
int cx[maxn];
int findpath(int u){
    FOR(i,1,ny)
        if(bmap[u][i]&&!bmask[i]){
            bmask[i]=1;
            if(cx[i]==-1||findpath(cx[i])){
                cx[i]=u;
                return 1;
            }
        }
    return 0;
}
int MaxMatch(){
    int res=0;
    FOR(i,1,nx){
            MT(bmask,false);
            res+=findpath(i);
        }
    return res;
}
int main(){
    int k,x,y;
    while(rd(k)&&k){
        rd2(nx,ny);
        MT(bmap,false);
        MT(bmask,false);
        MT(cx,0);
        MT(cx,-1);
        FOR(i,1,k){
            rd2(x,y);
            bmap[x][y]=1;
        }
        printf("%d
",MaxMatch()); } } /* 6 3 3 1 1 1 2 1 3 2 1 2 3 3 1 0 */