rt 稳定婚姻匹配问题

The Stable Marriage Problem

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>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int n;
char boy_name[30][2],girl_name[30][2];
int to_boy[26],to_girl[26];

int perfect_boy[30][30],perfect_girl[30][30];
int future_husband[30],future_wife[30];
int next[30];
queue<int> q;

void init()
{
    memset(boy_name,0,sizeof(boy_name));
    memset(girl_name,0,sizeof(girl_name));
    memset(to_boy,0,sizeof(to_boy));
    memset(to_girl,0,sizeof(to_girl));
    memset(perfect_boy,0,sizeof(perfect_boy));
    memset(perfect_girl,0,sizeof(perfect_girl));
    memset(future_husband,0,sizeof(future_husband));
    memset(future_wife,0,sizeof(future_wife));
    memset(next,0,sizeof(next));
    while(!q.empty()) q.pop();
}

void engage(int boy,int girl)
{
    int m=future_husband[girl];
    if(m)
    {
        future_wife[m]=0;
        q.push(m);
    }
    future_husband[girl]=boy;
    future_wife[boy]=girl;
}

bool lover(int boy,int m,int girl)
{
    for(int i=1;i<=n;i++)
    {
        if(perfect_boy[girl][i]==boy) return true;
        if(perfect_boy[girl][i]==m) return false;
    }
}

int main()
{
    int T_T,flag=0;
    char in[50];
    scanf("%d",&T_T);
    while(T_T--)
    {
        if(flag==0) flag=1;
        else putchar(10);
        init();
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",boy_name[i]);
            to_boy[boy_name[i][0]-'a']=i;
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%s",girl_name[i]);
            to_girl[girl_name[i][0]-'A']=i;
        }
        for(int i=0;i<n;i++)
        {
            scanf("%s",in);
            int boy=to_boy[in[0]-'a'];
            for(int j=2;j<n+2;j++)
            {
                int girl=to_girl[in[j]-'A'];
                perfect_girl[boy][j-1]=girl;
            }
            q.push(i+1);
        }
        for(int i=0;i<n;i++)
        {
            scanf("%s",in);
            int girl=to_girl[in[0]-'A'];
            for(int j=2;j<n+2;j++)
            {
                int boy=to_boy[in[j]-'a'];
                perfect_boy[girl][j-1]=boy;
            }
        }
        while(!q.empty())
        {
            int boy=q.front(); q.pop();
            int girl=perfect_girl[boy][++next[boy]];
            int m=future_husband[girl];
            if(m==0)
                engage(boy,girl);
            else
            {
                if(lover(boy,m,girl))
                    engage(boy,girl);
                else q.push(boy);
            }
        }
        for(int i=1;i<=n;i++)
        {
            int boy=to_boy[boy_name[i][0]-'a'];
            printf("%c %c\n",boy_name[i][0],girl_name[future_wife[boy]][0]);
        }
    }
    return 0;
}

HDOJ 1914 The Stable Marriage Problem,布布扣,bubuko.com

HDOJ 1914 The Stable Marriage Problem

原文：http://blog.csdn.net/ck_boss/article/details/35554999