|
Language:
The Stable Marriage Problem
Description 稳定婚姻系统问题如下
如果没有(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 |
这题是很经典的稳定婚姻系统问题,它的解法为“求婚-拒绝”算法：
======================================================================================================
稳定婚姻问题的经典算法为求婚-拒绝算法(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.