学步园

貌似又叫延迟认可算法？

问题模型及解答方法可以参考：

稳定婚姻问题

[0]引言 什么是算法 如何寻找稳定的婚姻搭配

大学招生问题模型也可以参考这个。

Poj 3487 The Stable Marriage Problem

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int N=30;

int n,data[N];
int gg[N][N];   //gg[i][j]=k  i男第j喜欢k女
int mm[N][N];   //mm[i][j]=k  j男是i女第k喜欢的
int glike[N];    //glike[i]=j  i男目前最喜欢j女
int mlike[N];    //mlike[i]=j  i女目前更喜欢j男
queue<int> q;

void Stable_marriage ()
{
	memset(glike,0,sizeof(glike));  //男生最喜欢的全部初始为0
	memset(mlike,-1,sizeof(mlike)); //所有女生都未被表白
	while (!q.empty())
	{
        int pm = q.front ();
		q.pop ();
		int pf = gg[pm][glike[pm]];  //pm男向当前喜欢的女生表白
		glike[pm]++;
		if (mlike[pf] < 0)  //还没有人向她表白
			mlike[pf] = pm;
		else if (mm[pf][mlike[pf]] < mm[pf][pm]) //对以前向她表白的人的喜欢程度高于现在的(数值小)
            q.push (pm);  //该男重新入队
		else
		{//否则将原来男入队,并重新分配
			q.push (mlike[pf]);
			mlike[pf] = pm;
		}
	}
	int i;
	for (i=0;i<26;i++)
		if (mlike[i]>-1)
			glike[mlike[i]] = i;
    for (i=0;i<n;i++)
		printf("%c %c\n",data[i]+'a',glike[data[i]]+'A');
	printf("\n");
}


int main ()
{
	int T,i,j;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
        char str[30];
		while (!q.empty())
			q.pop();
		for (i=0;i<n;i++)
		{
			scanf("%s",str);
			data[i]=str[0]-'a';
			q.push(data[i]);
		}
		sort(data,data+n);
		for (i=0;i<n;i++)
			scanf("%*s");
		for (i=0;i<n;i++)
		{
			scanf("%s",str);
			for (j=0;j<n;j++)
				gg[str[0]-'a'][j]=str[j+2]-'A';
		}
		for (i=0;i<n;i++)
		{
			scanf("%s",str);
			for (j=0;j<n;j++)
				mm[str[0]-'A'][str[j+2]-'a']=j;
		}
		Stable_marriage();
	}
    return 0;
}

Hdu 1522 Marriage is Stable

//#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

const int N=505;

int n,data[N];
int gg[N][N];   //gg[i][j]=k  i男第j喜欢k女
int mm[N][N];   //mm[i][j]=k  j男是i女第k喜欢的
int glike[N];    //glike[i]=j  i男目前最喜欢j女
int mlike[N];    //mlike[i]=j  i女目前更喜欢j男
queue<int> q;

void Stable_marriage ()
{
	memset(glike,0,sizeof(glike));  //男生最喜欢的全部初始为0
	memset(mlike,-1,sizeof(mlike)); //所有女生都未被表白
	while (!q.empty())
	{
        int pm = q.front ();
		q.pop ();
		int pf = gg[pm][glike[pm]];  //pm男向当前喜欢的女生表白
		glike[pm]++;
		if (mlike[pf] < 0)  //还没有人向她表白
			mlike[pf] = pm;
		else if (mm[pf][mlike[pf]] < mm[pf][pm]) //对以前向她表白的人的喜欢程度高于现在的(数值小)
            q.push (pm);  //该男重新入队
		else
		{//否则将原来男入队,并重新分配
			q.push (mlike[pf]);
			mlike[pf] = pm;
		}
	}
	for (int i=0;i<n;i++)
		if (mlike[i]>-1)
			glike[mlike[i]] = i;
}

int main ()
{
	while (~scanf("%d",&n))
	{
        char str[205];
        while (!q.empty())
            q.pop();
		map<string,int> gnum,mnum;
		string gname[N],mname[N];
        int i,j,gid=0,mid=0;  //男生编号,女生编号
		for (i=0;i<n;i++)
		{
			scanf("%s",str);
			gnum[str]=gid;
			gname[gid]=str;
			q.push(gid);
			for (j=0;j<n;j++)
			{
			    scanf("%s",str);
			    if (mnum.find(str)==mnum.end())
			    {
			        mname[mid]=str;
			        mnum[str]=mid++;
			    }
                gg[gid][j]=mnum[str];
			}
			gid++;
		}
		for (i=0;i<n;i++)
		{
			scanf("%s",str);
			int tmp=mnum[str];
			for (j=0;j<n;j++)
			{
			    scanf("%s",str);
			    mm[tmp][gnum[str]]=j;
			}
		}
		Stable_marriage();
		for (i=0;i<n;i++)
            cout<<gname[i]<<' '<<mname[ glike[i] ]<<endl;
        printf("\n");
	}
    return 0;
}