zoj1576_stable_matching.cpp

最近在acm.zju.edu.cn上通过的题目的代码

// zoj 1576
#include <iostream>
#include <string>
#include <map>
using namespace std;

int nb, ng, n;
map<string, int> boy;
map<string, int> girl;
string boymk[510], girlmk[510];

int a[510][510], rank[510][510], pose[510];
int vm1[505], vm2[505], input[510];

int find_boy(string s){
	if (boy.count(s) == 0){
		boymk[nb] = s;
		boy[s] = nb;
		nb++;
	}
	return boy[s];
}

int find_girl(string s){
	if (girl.count(s) == 0){
		girlmk[ng] = s;
		girl[s] = ng;
		ng++;
	}
	return girl[s];
}

int main(){
		int i, j, v1, v2, u, v;
		string s;
		while (cin >> n){
				nb = ng = 0;
				boy.clear();  girl.clear();
				for (i = 0; i < n; i++){
						cin >> s;
						v1 = find_boy(s);
                        input[i] = v1; 
						for (j = 0; j < n; j++){
                                cin >> s;
								v2 = find_girl(s);
                                a[v1][j] = v2;
                        }
                }
				for (i = 0; i < n; i++){
						cin >> s;
						v1 = find_girl(s);
						for (j = 0; j < n; j++){
								cin >> s;
								v2 = find_boy(s);
                                rank[v1][v2]=j;
                        }
                }
				memset(pose, 0, sizeof(pose));
				memset(vm1, -1, sizeof(vm1));
				memset(vm2, -1, sizeof(vm2));
				while(1){
						for (i = 0; i < n; i++) if (vm1[i] == -1) break;
						if (i == n) break;
						u = i;
						v = a[u][pose[u]++];
						if (vm2[v] == -1){
								vm2[v] = u;
								vm1[u] = v;
						}
						else if (rank[v][vm2[v]] > rank[v][u]){
								vm1[vm2[v]] = -1;
								vm2[v] = u;
								vm1[u] = v;
						}
				}
				for (i = 0; i < n; i++)
						cout << boymk[input[i]] << ' ' << girlmk[vm1[input[i]]] << endl;
				cout << endl;
        }
        return 0;
}