marriage is stable(稳定婚姻匹配).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

//rmw[i][j]代表i男对喜欢
//lwm[i][j]代表i女对j男的喜欢程度
const int MAX = 510;
int w,m,n;
int rmw[MAX][MAX];
int lmw[MAX][MAX], lwm[MAX][MAX]; 
int couple[MAX];
bool flag[MAX];
char sman[MAX][110], swoman[MAX][110];

bool dfs(int man)
{
	int i,woman;
	for(i=1;i<=n;i++) {
		woman = rmw[man][i];
		rmw[man][i] = -1;
		if(woman != -1) {
			int pre = couple[woman];
			couple[woman] = man;
			if(pre == -1) {
				return true;
			}
			if(lwm[woman][man] > lwm[woman][pre]) {
				if( dfs(pre) ) {
					return true;
				}
				return false;
			}
			couple[woman] = pre;
		}
	}
	return false;
}

int stable_matching()
{
	int i,match = 0;
	memset(couple,-1,sizeof(couple));
	for(i=1;i<=n;i++) {
		if( dfs(i) ) {
			match ++;
		}
	}
	return match;
}

queue<int> SQ;
void gale_shapley()
{
	int i,man,woman;
	while(!SQ.empty()) {
		SQ.pop();
	}
	memset(couple,-1,sizeof(couple));
	for(i=1;i<=n;i++) {
		SQ.push(i);
	}

	while(!SQ.empty()) {
		man = SQ.front();
		for(i=1;i<=n;i++) {
			if(rmw[man][i] != -1) {
				woman = rmw[man][i];
				rmw[man][i] = -1;

				int pre = couple[woman];
				if(pre == -1) {
					couple[woman] = man;
					SQ.pop();
					break;
				}
				else {
					if(lwm[woman][man] > lwm[woman][pre]) {
						SQ.pop();
						SQ.push(pre);
						couple[woman] = man;
						break;
					}
				}
			}
		}
	}//while
}

int find(char * who, char names[][110], int all)
{
	int i;
	for(i=1;i<=all;i++) {
		if(strcmp(who, names[i])==0) {
			return i;
		}
	}
	return -1;
}

int main()
{
	int i,j,bs,ws;
	char who[110];
	bool flag;
	while(scanf("%d", &n)==1) {
		ws = 0;
		bs = n;
		flag = true;
		for(i=1;i<=n;i++) {
			scanf("%s", sman[i]);
			for(j=1;j<=n;j++) {
				scanf("%s", who);
				int pos = find(who, swoman,ws);
				if(pos == -1) {
					ws ++;
					strcpy(swoman[ws], who);
					pos = ws;
				}
				lmw[i][pos] = n-j+1;
				rmw[i][j] = pos;
			}
		}

		for(i=1;i<=n;i++) {
			scanf("%s", who);
			int pos1 = find(who, swoman,ws);
			for(j=1;j<=n;j++) {
				scanf("%s", who);
				int pos2 = find(who, sman,bs);
				lwm[pos1][pos2] = n-j+1;
			}
		}

		stable_matching();
		//gale_shapley();
		for(i=1;i<=n;i++) {
			printf("%s %s\n", sman[ couple[i] ], swoman[i]);
		}
		printf("\n");
	}
}