题意:旅行公司决定夏天带n(1<=n<=800)个男人N个女人被选上去参加这个旅行。旅行公司有N辆车,并且每一辆车只能坐两个人,旅行社顾客服务部门
的领导决定让每辆车里坐一男一女, 这就是为什么他们决定让顾客列出自己的喜好。 假设我们已经把男人和女人进行了一次匹配,让每一个男人和一个女
人配对,每一个女人也只和一个男人配对。我们把这样的配对叫做“完美匹配”。如果在完美匹配当中,有一对男女没有相互匹配,但是比起当前的匹配,
他们更喜欢对方,那么这样的一对人就是不稳定的,给出男人和女人的喜好列表, 输出一个完美匹配并且没有不稳定的分配情况。
题解:Gale-Shapley稳定婚姻匹配n^2算法。一定有解。
Sure原创,转载请注明出处
#include <iostream> #include <cstdio> #include <string.h> #include <queue> #include <map> #include <string> using namespace std; const int maxn = 802; const int maxm = 12; int boylike[maxn][maxn],girllike[maxn][maxn]; int boychoice[maxn],girlchoice[maxn]; char boyname[maxn][maxm],girlname[maxn][maxm],str[maxm]; map <string , int> boy , girl; queue <int> Q; int n; void init() { boy.clear(); girl.clear(); while(!Q.empty()) Q.pop(); for(int i=1;i<=n;i++) { boychoice[i] = 1; girlchoice[i] = 0; } return; } void read() { string ss; int top = 0; for(int i=1;i<=n;i++) { scanf("%s",boyname[i]); ss = boyname[i]; boy[ss] = i; for(int j=1;j<=n;j++) { scanf("%s",str); ss = str; if(girl.find(ss) == girl.end()) { strcpy(girlname[++top] , str); girl[ss] = top; } boylike[i][j] = girl[ss]; } Q.push(i); } for(int i=1;i<=n;i++) { scanf("%s",str); ss = str; int id = girl[ss]; for(int j=0;j<n;j++) { scanf("%s",str); ss = str; girllike[id][boy[ss]] = n - j; } girllike[id][0] = 0; } return; } void solve() { while(!Q.empty()) { int cur = Q.front(); int hope = boylike[cur][boychoice[cur]]; if(girllike[hope][cur] > girllike[hope][girlchoice[hope]]) { Q.pop(); if(girlchoice[hope] != 0) { Q.push(girlchoice[hope]); boychoice[girlchoice[hope]]++; } girlchoice[hope] = cur; } else { boychoice[cur]++; } } puts("YES"); for(int i=1;i<=n;i++) { printf("%s %s\n",boyname[i] , girlname[boylike[i][boychoice[i]]]); } return; } int main() { while(~scanf("%d",&n)) { init(); read(); solve(); } return 0; }