杭電oj HDOJ 2063ジェットコースター(ハンガリー法二分図最大マッチング)

杭電oj HDOJ 2063ジェットコースター
テーマの出所:http://acm.hdu.edu.cn/showproblem.php?pid=2063
Problem Description
RPG girlsは今日、みんなで遊園地に遊びに行って、やっと夢のジェットコースターに乗ることができました.しかし、ジェットコースターの各列には2つの席しかありません.そして、女の子一人一人が男の子を探してパートナーをして彼女と一緒に座らなければなりません.しかし、女の子はそれぞれの考えを持っていて、例えば、RabbitはXHDやPQKとパートナーをしたいだけで、GrassはlinleやLLとパートナーをしたいだけで、PrincesssSnowは水域の波や偽クールとパートナーをしたいと思っています.経費の問題を考慮して、boss劉はパートナーを見つけた人だけをジェットコースターに乗らせることにした.他の人は、へへ、下に立って見ていただろう.賢いAcmer、ジェットコースターに乗れる組み合わせはどれくらいあるか計算してもらえますか?
Input
入力データの最初の行は3つの整数K,M,Nであり,それぞれ可能な組合せ数,女子の人数,男子の人数を表す.0 1<=NおよびM<=500である.次のK行は、行ごとに2つの数があり、それぞれ女子Aiが男子Bjとパートナーをしたいことを示しています.最後の0は入力を終了します.
Output
各グループのデータについて、ジェットコースターに乗れる最大の組み合わせ数を示す整数を出力します.
問題を解く構想.
本題は典型的な「二分図の最大マッチング」問題を解き,このような問題を解決する方法は「ハンガリー法」である.このような問題に関する概念は次のとおりです.https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E5%9B%BE次に、問題で示した「模範例」を使用して、具体的な解題手順を説明します.

問題を解く前に必ず「用例」の「組合せデータ図」を記憶しなければならない.本題のデータ量は大きくないので、ここでは「隣接マトリクス法」を用いて図のデータを記憶し、読者も自分で他の方法のコードを書くことができる.c o m b i n e = [ 1 1 1 1 0 1 1 0 0 ] combine=\left[\begin{matrix} 1 & 1 & 1\\1 & 0 & 1\\1 & 0 & 0\\\end{matrix}\right] combine=⎣⎡​111​100​110​⎦⎤​

それから順番に1番の女子学生に先に組み合わせの男子学生を選ばせて、選ぶのも順番に行って、だから1番の女子学生は1番の男子学生を選びました.

番は2番の女の子が選ばれる番で、最初は1番の男の子が見えました.この時、1番の男の子はもう1番の女の子に選ばれましたが、2番の女の子はやはり1番の男の子を選びたいと思っています(アルゴリズムが必要です).だから、今、選んだ1番の女の子を他の男の子に割り当てることができるかどうかを見て、1番の男の子を残してこの時選んだ2番の女の子に割り当てます.だから組み合わせ案は1番の女子学生と2番の男子学生、2番の女子学生と1番の男子学生に変わりました.

それから3番の女子学生が選び始めました.同じように2番の女子学生に割り当てられた1番の男子学生を見ました.同じ3番の女子学生も1番の男子学生を選びたいと思っています.同じように今回は2番の女子学生を他の男子学生に割り当てることができるかどうかを見てみましょう.2番の女子学生のもう一つの組み合わせの意思は3番の男子学生と、3番の男子学生はまだ選ばれていません.だからこの时の组み合わせの方案は1番の女子学生と2番の男子学生になって、2番の女子学生と3番の男子学生、3番の女子学生と1番の男子学生、この组み合わせは完成して、ジェットコースターに乗ることができる最大の组み合わせの数は3です!

上の4歩目で2番の女の子のもう一つの組み合わせを望む男性も前の女の子に選ばれたらどうしますか?では、その前の女の子に彼女の組み合わせを変えて、男子学生を2番の女子学生に譲って、前の女子学生は組み合わせを変える時また“男子学生がすでに選ばれました”の情況に出会ったら、引き続き前に組み合わせの方案を変えて、1つの実行可能な方案を見つけるまで、あるいは女子学生はすでに他の組み合わせの意志がないまで
まとめると、本題の2つのポイントは「組み合わせを解く」と「前へ遡る」です!
本人のC++ソリューション

#include 
#include 
using namespace std;

bool find(int);
bool combine[501][501];
bool mark[501];					//            ，         
int boy[501];					//               
int M, N;						//             

int main()
{
     
	int K, i, count;
	int Ai, Bj;
	while (cin >> K) {
     
		if (!K) {
     
			break;
		}
		cin >> M >> N;
		//    “    ”
		for (i = 1; i < 501; i++) {
     
			memset(combine[i], 0, sizeof(combine[i]));
		}
		//    “    ”  
		memset(boy, 0, sizeof(boy));
		count = 0;
		for (i = 0; i < K; i++) {
     
			cin >> Ai >> Bj;
			combine[Ai][Bj] = 1;
		}
		for (i = 1; i <= M; i++) {
     
			//             
			memset(mark, 0, sizeof(mark));
			if (find(i)) {
     
				count++;
			}
		}
		printf("%d
", count);
	}
	return 0;
}

bool find(int n)
{
     
	int i;
	for (i = 1; i <= N; i++) {
     
		if (combine[n][i] && !mark[i]) {
     
			mark[i] = true;
			//    ：             
			//    ：                        
			if (boy[i] == 0 || find(boy[i])) {
     
				boy[i] = n;
				return true;
			}
		}
	}
	return false;
}

コードはHDOJプラットフォームを通じて検査を実行して、例えば間違いを発見して、指摘と訂正を歓迎して、ありがとうございます!