题目给出n个男的和n个女的各自喜欢对方的程度,让你输出一个最佳搭配,使得他们所有人的婚姻都是稳定的。
所谓不稳婚姻是说,比如说有两对夫妇M1,F1和M2,F2,M1的老婆是F1,但他更爱F2;而F2的老公虽说是M2.但她更爱M1,这样的婚姻就是不稳婚姻,M1和F2理应结合,他们现在各自的婚姻都是错误的。
整个算法基于,男性轮流向女性求婚,每次求婚对象都是没有拒绝过自己且自己最喜欢的女性。而女性对于每个求婚者,若她是单身,则接受,否则,就看她更喜欢当前求婚者还是她的未婚夫,选择更好的那个。
这种执行过程之后,男的都会追到自己最喜欢的女性,而女性都会得到不会太差的男性= =,并且可以证明,这个婚姻是稳定的。。。
#include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int maxn=1000+10; int pref[maxn][maxn],order[maxn][maxn],next[maxn]; int future_husband[maxn],future_wife[maxn]; queue<int> q; void engage(int man,int woman) { int m=future_husband[woman]; if(m) { future_wife[m]=0; q.push(m); } future_wife[man]=woman; future_husband[woman]=man; } int id_man[555]; int id_woman[555]; char str[555]; int main() { int cas,n; char A; scanf("%d",&cas); while(cas--) { scanf("%d",&n); vector<char> v; for(int i=1;i<=n;i++) {cin>>A;id_man[A]=i;v.push_back(A);} for(int i=1;i<=n;i++){cin>>A;id_woman[A]=i;} for(int i=1;i<=n;i++) { scanf("%s",str); int idm=id_man[str[0]]; for(int j=1;j<=n;j++) { int idw=id_woman[str[j+1]]; pref[idm][j]=idw; } next[idm]=1; future_wife[idm]=0; q.push(idm); } for(int i=1;i<=n;i++) { scanf("%s",str); int idw=id_woman[str[0]]; for(int j=1;j<=n;j++) { int idm=id_man[str[j+1]]; order[idw][idm]=j; } future_husband[idw]=0; } while(!q.empty()) { int man=q.front();q.pop(); int woman=pref[man][next[man]++]; if(!future_husband[woman]) engage(man,woman); else if(order[woman][man]<order[woman][future_husband[woman]]) engage(man,woman); else q.push(man); } while(!q.empty()) q.pop(); for(int i=0;i<n;i++) { printf("%c %c\n",v[i],future_wife[v[i]-'a'+1]+'A'-1); } if(cas) puts(""); } return 0; }谁告白谁占便宜,屌丝男快去告白吧。。
poj 3478 The Stable Marriage Problem 稳定婚姻问题,布布扣,bubuko.com
poj 3478 The Stable Marriage Problem 稳定婚姻问题
原文:http://blog.csdn.net/t1019256391/article/details/37564761