算法 稳定婚姻问题 The Stable Marriage Problem 木

The Stable Marriage Problem

Description

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 (mf) 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 C

a B
b A
c C

poj 3487 http://poj.org/problem?id=3487

稳定婚姻问题:所谓的稳定是指在当前所有的匹配中,不存在a(m,f), b(m,f),a.m更喜欢b.f而且a.f更喜欢b.m;
解决这个问题用的是模拟的方法。即男生先表白,然后女生在选取对自己表白的男生中自己最喜欢的那个。如果男生已经匹配则不可以表白了,但女生可以接受的更好的男生,这样会造成该女生原来的对象未匹配,所以该男的得继续表白了。。。
View Code
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 #define maxn 35
 8 int n;
 9 int mlove[maxn][maxn], flove[maxn][maxn];
10 // 男生对女生的喜欢程度 和 女生对男生的喜欢程度
11 
12 void init(){
13     char str[100];
14     scanf("%d", &n);
15     getchar();   gets(str);
16     for ( int i=0; i<n; ++i ) {
17          scanf("%s", str);
18          int u;
19          for ( int j=0, N=0; str[j]; ++j ){
20              if(islower(str[j] ) )  u = str[j]-'a';
21              else if(isupper(str[j]) )
22                 mlove[u][N++] = str[j]-'A';
23          }
24     }
25     for ( int i=0; i<n; ++i ) {
26          scanf("%s", str);
27          int u;
28          for ( int j=0, N=0; str[j]; ++j){
29             if(isupper(str[j]) ) u = str[j]-'A';
30             else if(islower(str[j]) )
31               flove[u][str[j]-'a' ] = N++; // 该男的在女生心中的位置,越小越喜欢
32          }
33     }
34 }
35 
36 int pos[maxn]; // 男的已经表白了的人数
37 int fGetLove[maxn][maxn]; //女生得到表白的男生的号码
38 int mans[maxn], fans[maxn];// 保存male answer 和 female answer
39 
40 void solve(){
41     memset(pos, 0, sizeof pos);
42     memset(mans, -1, sizeof mans); //初始未配对结果是-1
43     memset(fans, -1, sizeof fans);
44     while( 1 ) { // 表白开始
45          for ( int i=0; i<n; ++i )
46            fGetLove[i][0] = 0; // 女生得到表白的个数
47          bool ff = 1;
48          for ( int i=0; i<n; ++i ) if(pos[i] < n && mans[i] == -1){
49              int v = mlove[i][pos[i]++ ];
50              fGetLove[v][++fGetLove[v][0] ] = i;
51              ff = 0;
52          }
53          if( ff ) break;
54 
55          // 女生开始处理表白关系;
56          for ( int i=0; i<n; ++i ) if(fGetLove[i][0] ) {
57               int minn = 30, tt;
58               for ( int j=1; j<=fGetLove[i][0]; ++j )
59               {
60                   int v = fGetLove[i][j];
61                   if(minn > flove[i][v] )
62                     minn = flove[i][v], tt = v;
63               }
64               // 当前女生已经有了匹配对象,所以minn要和该对象的映射比较
65               if(~fans[i] && minn > flove[i][fans[i] ]) continue;
66               if( ~fans[i] ) mans[fans[i] ] = -1; //
67               fans[i] = tt;  mans[tt] = i;
68          }
69     }
70     for ( int i=0; i<n; ++i )
71        printf("%c %c\n", i+'a', mans[i]+'A');
72 }
73 
74 int main(int argc, char**argv){
75     int T; scanf("%d", &T);
76     while( T-- ) {
77          init();
78          solve();
79          if( T ) puts("");
80     }
81     //system("pause");
82     return (EXIT_SUCCESS);
83 }

 同样的问题有:

hdoj 1522 http://acm.hdu.edu.cn/showproblem.php?pid=1522

codechef  http://www.codechef.com/AUG12/problems/BLOCKING


原文地址:https://www.cnblogs.com/TengXunGuanFangBlog/p/The_Stable_Marriage_Problem.html