ZOJ 1576(稳定婚姻系统-重名)

Marriage is Stable

Time Limit: 5 Seconds
Memory Limit:
32768 KB Special Judge


Albert, Brad, Chuck are happy bachelors who are in love with Laura, Marcy, Nancy. They all have three choices. But in fact, they do have some preference in mind. Say Albert, he likes Laura best, but that doesn't necesarily mean Laura likes him. Laura likes
Chuck more than Albert. So if Albert can't marry Laura, he thinks Nancy a sensible choice. For Albert, he orders the girls Laura > Nancy > Marcy.

For the boys:

Albert: Laura > Nancy > Marcy
Brad: Marcy > Nancy > Laura
Chuck: Laura > Marcy > Nancy

For the girls:

Laura: Chuck > Albert > Brad
Marcy: Albert > Chuck > Brad
Nancy: Brad > Albert > Chuck

But if they were matched randomly, such as

Albert <-> Laura
Brad <-> Marcy
Chuck <-> Nancy

they would soon discover it's not a nice solution. For Laura, she likes Chuck instead of Albert. And what's more, Chuck likes Laura better than Nancy. So Laura and Chuck are likely to come together, leaving poor Albert and Nancy.

Now it's your turn to find a stable marriage. A stable marriage means for any boy G and girl M, with their choice m[G] and m[M], it will not happen that rank(G, M) < rank(G, m[G]��and rank(M, G) < rank(M, m[M]).

Input

Each case starts with an integer n (1 <= n <= 500), the number of matches to make.

The following n lines contain n + 1 names each, the first being name of the boy, and rest being the rank of the girls.

The following n lines are the same information for the girls.

Process to the end of file.

Output

If there is a stable marriage, print n lines with two names on each line. You can choose any one if there are multiple solution. Print "Impossible" otherwise.

Print a blank line after each test.

Sample Input

3
Albert Laura Nancy Marcy
Brad Marcy Nancy Laura
Chuck Laura Marcy Nancy
Laura Chuck Albert Brad
Marcy Albert Chuck Brad
Nancy Brad Albert Chuck

Sample Output

Albert Nancy
Brad Marcy
Chuck Laura

这题就是稳定婚姻系统,

注意有同名的男女。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
#include<queue>
#include<iostream>
#include<map>
#include<string>
using namespace std;
#define MAXN (2000+10)
int n;
queue<int> q;
map<string,int> hpos_male,hpos_female;

int female_like[MAXN][MAXN];  //SIS
int male_like[MAXN][MAXN];    //SSI
int match[MAXN];
string a[MAXN];
int main()
{
//	freopen("zoj1576.in","r",stdin);
	while (scanf("%d",&n)!=EOF)
	{
		hpos_male.clear();
		hpos_female.clear();
		memset(match,0,sizeof(match));
		int size=n+1;
		for (int i=1;i<=n;i++)
		{
			cin>>a[i];hpos_male[a[i]]=i; q.push(i);
			for (int j=1;j<=n;j++)
			{
				string s;
				cin>>s;
				if (i==1)
				{
					hpos_female[s]=size;
					a[size]=s;
					size++;
				}
				male_like[i][j]=hpos_female[s];
			}
		}
		for (int i=n+1;i<=2*n;i++)
		{
			string sg;
			cin>>sg;
			for (int j=1;j<=n;j++)
			{
				string s;
				cin>>s;
				female_like[hpos_female[sg]][hpos_male[s]]=j;
			}
		}
		/*
		for (int i=n+1;i<=2*n;i++)
		{
			for (int j=1;j<=n;j++)
				cout<<female_like[make_pair(a[i],a[j])]<<' ';
			cout<<endl;
		}
		*/
		while (!q.empty())
		{
			int now=q.front();
			q.pop();
			for (int j=1;j<=n;j++)
			{
				int v=male_like[now][j];
				if (!match[v])
				{
					match[now]=v;match[v]=now;//cout<<now<<' '<<v<<endl;
					break;
				}
				else if (female_like[v][match[v]]>female_like[v][now])
				{
					q.push(match[v]);
					match[match[v]]=0;
					match[now]=v;match[v]=now;//cout<<now<<' '<<v<<endl;
					break;
				}
			}
		}
		for (int i=1;i<=n;i++)
		{
			cout<<a[i]<<' '<<a[match[i]]<<endl;
		}
		printf("n");
	}
	return 0;
}


POJ 3487(稳定婚姻问题)

Language:
The Stable Marriage Problem
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 1941   Accepted: 827

Description

稳定婚姻系统问题如下

  • 集合M 表示n个男性;
  • 集合 F 表示n个女性;
  • 对于每个人我们都按异性的中意程度给出一份名单(从最中意的到最不中意的).

如果没有(mf) , f ∈ F,m ∈ M f对m比对她的配偶中意的同时mf比对他的配偶更加中意,那这个婚姻是‘稳定’的.如果一个稳定配对不存在另一个稳定婚姻配对,其中所有的男性的配偶都比现在强,那么这个稳定配对称为男性最优配对。

Input

第一行为数据数.

对于每组数据,第一行为n (0 < n < 27).接下来一行依次为男性的名字(小写字母)和女性的名字(大写字母)接下来 n 行为每个男性的中意程度名单(从大到小),接下来n行是女性的中意程度名单(同上).

Output

输出一组男性最优配对,男性按字典序从小到大排列,每行为“男性名 女姓名”的形式;

每数据后输出一空行。

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

Source

这题是很经典的稳定婚姻系统问题,它的解法为“求婚-拒绝”算法:

======================================================================================================

稳定婚姻问题的经典算法为求婚-拒绝算法(propose-and-reject algorithm),即
男士按自己喜欢程度从高到低依次给每位女士主动求婚,直到有一个接受他。女士每
次遇到比当前配偶更差的男士时拒绝他,遇到更喜欢的男士时就接受他,并抛弃以前
的配偶。被抛弃的男士继续按照列表向剩下的女士依次求婚,直到所有人都有配偶。
看起来女士更有选择权,但实际上最后得到的结果是男士最优(man-optimal)的。下
面我们详细描述这一算法并证明相应的结论。
如果算法最后得到了一个匹配,那么它一定是稳定的。为了证明这一点,我们首
先注意到随着算法的执行,每位女士的配偶越来越好,而每位男士的配偶越来越差。
因此假设男士u和女士v形成不稳定对,u一定曾经向v求过婚,但被拒绝。这说明v当时
的配偶比u更好,因此算法结束后的配偶一定仍比u好,和不稳定对的定义矛盾。
下面我们只需要说明算法一定成功结束,即不会存在一位男士u,使得他向所有
女士求婚后仍为单身。假设存在这样的人,设其中最后一次被抛弃时刻最晚的男士
为u,则他最后一次被抛弃时无配偶,因此当时一定存在女士v也没有配偶。由于v是单
身的,所以一定没有人向她求过婚,因此v还在u的考虑范围之中,以后会向v求婚。到
432 图论问题和算法
时u会再次有配偶,要么还将被抛弃一次,要么最后不会单身,无论哪种情况都将产生
矛盾。
这样,我们证明了算法一定得到稳定匹配。时间复杂度显然是O(n2),因此每个男
士最多考虑每个女士各一次,每次的时间复杂度均为O(1)。显然这已经是时间复杂度
的下限了,因为输入是O(n2)的。
如果存在一个稳定匹配使得男士i和女士j配对,则称(i,j)是稳定对。对于每个男
士i,设所有稳定对(i,j)中i 最喜欢的女士为best(i),则可以证明这里给出的算法对让每
位男士i与best(i)配对。对于所有男士来说,不会有比这更好的结果了,而对于女士则
恰恰相反——对于她们来说不会有比这更糟的结果了。

=================================================================================================================


Program p3487;
const
   maxn=26;
var
   tt,n,i,j,k:longint;
   nam:array[1..2,1..maxn] of char;
   female_like:array['A'..'Z','a'..'z'] of longint;
   male_like:array['a'..'z',1..maxn] of char;

   a:array['a'..'z'] of char;
   b:array['A'..'Z'] of char;

   s:string;
   c:char;
   q:array[1..maxn*maxn] of char;
   h,t:longint;
   now,v:char;
begin
   readln(tt);
   while (tt>0) do
   begin
      fillchar(a,sizeof(a),' ');
      fillchar(b,sizeof(b),' ');
      readln(n);
      for k:=1 to 2 do
         for i:=1 to n do
         begin
            read(nam[k,i]);
            read(c);
         end;
      readln;
      for i:=1 to n do
      begin
         readln(s);
         for j:=3 to length(s) do male_like[s[1],j-2]:=s[j];
      end;
      for i:=1 to n do
      begin
         readln(s);
         for j:=3 to length(s) do female_like[s[1],s[j]]:=n+1-(j-2);
      end;

      h:=1;t:=n;
      for i:=1 to n do q[i]:=nam[1,i];
      while h<=t do
      begin
         now:=q[h];
         for i:=1 to n do
         begin
            v:=male_like[now,i];
            if (b[v]=' ') then
            begin
               a[now]:=v;
               b[v]:=now;
               break;
            end;
            if (female_like[v,b[v]]<female_like[v,now]) then
            begin
               inc(t);
               q[t]:=b[v];
               a[b[v]]:=' ';
               a[now]:=v;
               b[v]:=now;
               break;
            end;
         end;
         inc(h);
      end;


      for now:='a' to 'z' do if a[now]<>' ' then writeln(now,' ',a[now]);
      writeln;


      dec(tt);
   end;

end.