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
Sample Output
ACcode:
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であり,それぞれ可能な組合せ数,女子の人数,男子の人数を表す.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
*/