POJ 3487(稳定婚姻有关问题)

POJ 3487(稳定婚姻问题)

Language:

The Stable Marriage Problem

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1941		Accepted: 827

Description

稳定婚姻系统问题如下

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

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

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

Southeastern Europe 2007

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

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

稳定婚姻问题的经典算法为求婚-拒绝算法(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.

POJ 3487(稳定婚姻有关问题)

相关推荐