HDU 2063ジェットコースター(二分マッチング-ハンガリーアルゴリズム)

2384 ワード
ジェットコースター
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16627    Accepted Submission(s): 7254
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 

   
   
   
   

    
    
    
    6 3 3
1 1
1 2
1 3
2 1
2 3
3 1
0

 
Sample Output 

   
   
   
   

    
    
    
    3

 
Author
PrincessSnow
 
Source
RPG特別練習試合
 
Recommend
lcy   |   We have carefully/49386 selected several similar problems for you:   1068  1083  2444  1281  1150 
http://www.w2bc.com/Article/49386あ、二分マッチングの初心者は、前のリンクで詳しく説明しているような気がします.
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int map[1100][1100],ok[1100],vis[1100];
int m,n;
bool find(int x)
{
	for(int i=1;i<=n;i++)
	{
		if(map[x][i]==1&&!vis[i])//vis        
		{
			vis[i]=1;
			if(!ok[i])//        
			{
				ok[i]=x;
				return true;
			}
			else
			{
				if(find(ok[i])==true)//        
				{
					ok[i]=x;
					return true;
				}
			}
		}
	}
	return false;
}
int main()
{
	int k,a,b,i;
	while(scanf("%d",&k),k)
	{
	    scanf("%d%d",&m,&n);
	
		memset(ok,0,sizeof(ok));
		memset(map,0,sizeof(map));
		
		for(i=1;i<=k;i++)
		{
			scanf("%d%d",&a,&b);
			map[a][b]=1;
		 } 
		 int ans=0;
		 for(i=1;i<=m;i++)
		 {
		 	memset(vis,0,sizeof(vis));
		 	if(find(i)==true)
		 	{
		 		ans++;
			 }
		 	
		 }
		 printf("%d
",ans);
	}
	return 0;
}

Think In Javaノート7 Holding Your Objects
Kotlin常用文法