2013
12-27

# 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.

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.

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.

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

a A
b B
c C

a B
b A
c C

**********************************************************************************

#include<iostream>
using namespace std ;
const int N = 40 ;
struct male
{
int f,rev[N],tag;
}m[N];
struct female
{
int tag,temp,val,wait[N];
}f[N];
int n , t , k , mf[N][N] , fm[N][N];
char ch[N];
bool ok()
{
for(int i=1;i<=26;i++)
if(m[i].f==0&&m[i].tag>0) return true ;
return false ;
}
int main()
{
int T ;
scanf("%d",&T) ;
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=26;i++)
f[i].tag=0,m[i].tag=0;
for(int i=1;i<=n;i++)
{
scanf("%s",&ch);
t = ch[0]-'a' + 1 ;
m[t].f=0 , m[t].tag=t;
memset(m[t].rev,0,sizeof(m[t].rev));
}
for(int i=1;i<=n;i++)
{
scanf("%s",&ch);
t = ch[0]-'A' + 1 ;
f[t].tag = t ;
f[t].temp = 0 ;
f[t].val = 30 ;
memset(f[t].wait,0,sizeof(f[t].wait));
}
for(int i=1;i<=n;i++)
{
scanf("%s",&ch);
t = ch[0] - 'a' + 1 ;
for(int j=2;j<=n+1;j++)
mf[t][j-1] = ch[j] -'A' + 1 ;
}
for(int i=1;i<=n;i++)
{
scanf("%s",&ch);
t = ch[0] - 'A' + 1 ;
for(int j=2;j<=n+1;j++)
fm[t][j-1] = ch[j] -'a' + 1 ;
}
while(ok())
{
for(int i=1;i<=26;i++)
{
if(m[i].f==0&&m[i].tag>0)
{
for(int j=1;j<=n;j++)
{
t = mf[i][j] ;
if(m[i].rev[t]==0)
{
m[i].rev[t] = 1 ;
m[i].f = 1 ;
k = ++f[t].wait[0] ;
f[t].wait[k] = i ;
break;
}
}
}
}
for(int i=1;i<=26;i++)
{
if(f[i].tag>0)
{
for(int j=1;j<=f[i].wait[0];j++)
{
t = f[i].wait[j] ;
for(k=1;k<=n;k++)
{
if(fm[i][k]==t)  break;
}
if(f[i].val>k)
{
m[f[i].temp].f = 0 ;
f[i].temp = t ;
f[i].val = k ;
}
else m[t].f = 0 ;
}
f[i].wait[0] = 0 ;
}
}
}
int out[N];
memset(out,0,sizeof(out));
for(int i=1;i<=26;i++)
{
if(f[i].tag>0)
{
int j = f[i].temp ;
out[j] = i ;
}
}
for(int i=1;i<=26;i++)
{
if(out[i]) printf("%c %c/n",i-1+'a',out[i]-1+'A');
}
if(T) printf("/n");
}
return 0 ;
}

1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

3. #include <stdio.h>
int main(void)
{
int arr[] = {10,20,30,40,50,60};
int *p=arr;
printf("%d,%d,",*p++,*++p);
printf("%d,%d,%d",*p,*p++,*++p);
return 0;
}

为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下？