POJ 3487(稳定婚姻问题)
Language:The Stable Marriage ProblemTime Limit: 1000MS Memory Limit: 65536KTotal 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
23a b c A B Ca:BACb:BACc:ACBA:acbB:bacC:cab3a b c A B Ca:ABCb:ABCc:BCAA:bacB:acbC:abc
Sample Output
a Ab Bc Ca Bb Ac 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.
