hdu 2063ジェットコースター(私の最初の二分図)
ジェットコースター
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3105 Accepted Submission(s): 1298
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
最も簡単な二分図は、私が初めて書いた二分図でもあります.初めて作るのは少し難しいですが、後で作るのはそんなに難しくありません.二分図私個人の理解は:一つ一つマッチングして、もしあの人がマッチングされたら、それにマッチする人を探して他の人を探してマッチングできるかどうかを見て、絶えず探して、これらは拡張路と呼ばれているようで、定義はまだあまり見ていないので、まず簡単な問題をしました.
リンク:http://acm.hdu.edu.cn/showproblem.php?pid=2063
コード:
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3105 Accepted Submission(s): 1298
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
最も簡単な二分図は、私が初めて書いた二分図でもあります.初めて作るのは少し難しいですが、後で作るのはそんなに難しくありません.二分図私個人の理解は:一つ一つマッチングして、もしあの人がマッチングされたら、それにマッチする人を探して他の人を探してマッチングできるかどうかを見て、絶えず探して、これらは拡張路と呼ばれているようで、定義はまだあまり見ていないので、まず簡単な問題をしました.
リンク:http://acm.hdu.edu.cn/showproblem.php?pid=2063
コード:
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
const int N = 505;
bool map[N][N], flag[N];
int pre[N];
int n, m, num;
// （ ）
int find(int cur) //cur
{
int i;
for(i = 1; i <= m; i++) //
{
if(map[cur][i] && !flag[i]) //
{
flag[i] = true; // ，
if(pre[i] == -1 || find(pre[i]))// or -> ok
{
pre[i] = cur; // [i] cur
return 1;
}
}
}
return 0;
}
int main()
{
int i, girl, boy, sum;
while(scanf("%d", &num), num)
{
scanf("%d %d", &n, &m); //n ，m
memset(map, false, sizeof(map));
memset(pre, -1, sizeof(pre));
for(i = 0; i < num; i++)
{
scanf("%d %d", &girl, &boy);
map[girl][boy] = true; //
}
sum = 0;
for(i = 1; i <= n; i++) //
{
memset(flag, 0, sizeof(flag)); // 0
sum += find(i);
}
printf("%d
", sum);
}
return 0;
}