稳定婚姻问题 Poj 3487 The Stable Marriage Problem + Hdu 1522 Marriage is Stable (二分图稳定匹配)

秒速五厘米 2022-09-19 05:18 8阅读 0赞

貌似又叫延迟认可算法？

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

[稳定婚姻问题][Link 1]

[\[0\]引言 什么是算法 如何寻找稳定的婚姻搭配][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;
    }

[Link 1]: http://blog.csdn.net/yuhailin060/article/details/5405420
[0_ _]: http://www.matrix67.com/blog/archives/2976