【杭電oj】ジェットコースター(二分図最大マッチング、ハンガリーアルゴリズム)
2358 ワード
ジェットコースター
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16644 Accepted Submission(s): 7265
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
Author
PrincessSnow
Source
RPG特別練習試合
新しいアルゴリズムを感じて、感じはまあまあで、まだ受け入れることができます==
この問題はこのアルゴリズムの最も基礎的な問題でしょう.まだ頑張る必要があるようですね.
コードは次のとおりです.
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16644 Accepted Submission(s): 7265
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
Author
PrincessSnow
Source
RPG特別練習試合
新しいアルゴリズムを感じて、感じはまあまあで、まだ受け入れることができます==
この問題はこのアルゴリズムの最も基礎的な問題でしょう.まだ頑張る必要があるようですね.
コードは次のとおりです.
#include <cstdio>
#include <cstring>
int fr[505][505]; //
int used[505];
int F[505]; //
int k,m,n; // ， ，
bool find(int x)
{
for (int i = 1 ; i <= n ; i++)
{
if (fr[x][i] && !used[i]) //
{
used[i] = 1; //
if (F[i]) // 0
{
if (find(F[i])) // （ ）
{
F[i] = x;
return true;
}
}
else // ，
{
F[i] = x;
return true;
}
}
}
return false;
}
int main()
{
int ans;
while (~scanf ("%d",&k) && k)
{
scanf ("%d %d",&m,&n);
memset (fr,0,sizeof (fr));
memset (F,0,sizeof (F));
ans = 0;
while (k--)
{
int x,y;
scanf ("%d %d",&x,&y);
fr[x][y] = 1;
}
for (int i = 1 ; i <= m ; i++)
{
memset (used,0,sizeof (used));
if (find(i))
ans++;
}
printf ("%d
",ans);
}
return 0;
}