合宿チームスペシャル(6)1009ジェットコースター
2234 ワード
ジェットコースター
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16130 Accepted Submission(s): 7069
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): 16130 Accepted Submission(s): 7069
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>
#include <algorithm>
using namespace std;
const int maxn = 500+10;
int uN,vN;
int g[maxn][maxn],linker[maxn];
bool used[maxn];
bool dfs(int u)
{
int v;
for(v=1; v<=vN; v++)
if(g[u][v] && !used[v])
{
used[v] = true;
if(linker[v]==-1 || dfs(linker[v]))
{
linker[v] = u;
return true;
}
}
return false;
}
int hungary()
{
int res = 0;
int u;
memset(linker,-1,sizeof(linker));
for(u=1; u<=uN; u++)
{
memset(used,0,sizeof(used));
if(dfs(u)) res++;
}
return res;
}
int main()
{
int k,u,v;
while(scanf("%d",&k)&&k)
{
scanf("%d%d",&uN,&vN);
memset(g,0,sizeof(g));
for(int i=0; i<k; i++)
{
scanf("%d%d",&u,&v);
g[u][v] = 1;
}
int ans = hungary();
printf("%d
",ans);
}
return 0;
}