HDU 1914 The Stable Marriage Problem_综合

The stable marriage problem consists of matching members of two different sets according to the member’s preferences for the other set’s members. The input for our problem consists of:

a set M of n males;
a set F of n females;

for each male and female we have a list of all the members of the opposite gender in order of preference (from the most preferable to the least).
A marriage is a one-to-one mapping between males and females. A marriage is called stable, if there is no pair (m, f) such that f ∈ F prefers m ∈ M to her current partner and m prefers f over his current partner. The stable marriage A is called male-optimal if there is no other stable marriage B, where any male matches a female he prefers more than the one assigned in A.

Given preferable lists of males and females, you must find the male-optimal stable marriage.

Input

The first line gives you the number of tests. The first line of each test case contains integer n (0 < n < 27). Next line describes n male and n female names. Male name is a lowercase letter, female name is an upper-case letter. Then go n lines, that describe preferable lists for males. Next n lines describe preferable lists for females.

Output

For each test case find and print the pairs of the stable marriage, which is male-optimal. The pairs in each test case must be printed in lexicographical order of their male names as shown in sample output. Output an empty line between test cases.

Sample Input

2
3
a b c A B C
a:BAC
b:BAC
c:ACB
A:acb
B:bac
C:cab
3
a b c A B C
a:ABC
b:ABC
c:BCA
A:bac
B:acb
C:abc

Sample Output

a A
b B
c Ca B
b A
c C

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

稳定婚姻问题~

神奇的算法。但是很好实现啊。

稳定婚姻问题就是题里面描述的这个。

我们考虑所有男性都配对到最优结果的情况，即题目要求的情况。

我们先把所有男性入队，女性的配对表me全部赋值为-1。

每次取出一男子，然后从好感度高到好感度低的女子依次配对，如果该女子me尚为-1，或者该男子在该女子处的好感度比该女子正在交往的男子高，就让该女子与该男子配对，原来的交往对象就没有配偶，加入队列。这样，最后一定能把所有人配对。

注意人里面有标号为0的，所以me要赋值为-1而不是0。

最后一组不能输出空行。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;int t,n,a[26][26],c[26][26],ma[26],fe[26],x,len;
bool b1[26],b2[26],b[27][26],flag;
char s[26];queue<int> q;bool pei(int u,int v)
{b[u][v]=1;if(fe[v]==-1){fe[v]=u;ma[u]=v;return 1;}if(c[v][fe[v]]>c[v][u]){q.push(fe[v]);fe[v]=u;ma[u]=v;return 1;}return 0;
}int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);memset(b1,0,sizeof(b1));memset(b2,0,sizeof(b2));memset(b,0,sizeof(b));memset(fe,-1,sizeof(fe));memset(c,127/3,sizeof(c));for(int i=1;i<=n;i++) scanf("%s",s),b1[s[0]-'a']=1,q.push(s[0]-'a');for(int i=1;i<=n;i++) scanf("%s",s),b2[s[0]-'A']=1;for(int i=1;i<=n;i++){scanf("%s",s);x=s[0]-'a';a[x][0]=strlen(s);for(int i=2;i<a[x][0];i++) a[x][i-1]=s[i]-'A';a[x][0]-=2;}for(int i=1;i<=n;i++){scanf("%s",s);x=s[0]-'A';len=strlen(s);for(int i=2;i<len;i++) c[x][s[i]-'a']=i-1;}while(!q.empty()){x=q.front();q.pop();flag=0;for(int i=1;i<=a[x][0];i++)if(!b[x][a[x][i]] && pei(x,a[x][i])){flag=1;break;}if(!flag) q.push(x);}for(int i=0;i<26;i++) if(b1[i]) printf("%c %c\n",i+'a',ma[i]+'A');if(t) puts("");}return 0;
}