二分図のハンガリーアルゴリズムHDU 2063(裸テンプレート、追加待ち)
2831 ワード
ジェットコースター
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16742 Accepted Submission(s): 7314
Problem 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
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16742 Accepted Submission(s): 7314
Problem 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
： ， 。
： ：
#include <stdio.h>
#include <string.h>
int k,m,n;
int map[505][505];
int vis[505];
int lianxi[505];
int suan(int x)// ： （lianxi[j]==0）, （suan(lianxi[j])）
{
for(int j=1; j<=n; j++)
{
if(!vis[j]&&map[x][j])// ，
{
vis[j]=1;
if(lianxi[j]==0||suan(lianxi[j]))//
{
lianxi[j]=x;
return 1;
}
}
}
return 0;
}
int main()
{
while(scanf("%d",&k)!=EOF)
{
if(k==0)
break;
scanf("%d%d",&m,&n);
memset(map,0,sizeof(map));
memset(lianxi,0,sizeof(lianxi));
while(k--)
{
int a,b;
scanf("%d%d",&a,&b);
map[a][b]=1;
}
int count=0;
for(int i=1; i<=m; i++)
{
memset(vis,0,sizeof(vis));
if(suan(i))
count++;
}
printf("%d
",count);
}
}