当前位置: 首页 > >

信与信封问题

发布时间:

题目大意



John先生晚上写了n封信,并相应地写了n个信封将信装好,准备寄出。但是,第二天John的儿子Small John将这n封信都拿出了信封。不幸的是,Small John无法将拿出的信正确地装回信封中了。


?


将Small John所提供的n封信依次编号为1,2,…,n;且n个信封也依次编号为1,2,…,n。假定Small John能提供一组信息:第i封信肯定不是装在信封j中。请编程帮助Small John,尽可能多地将信正确地装回信封。

题解

首先找出最大匹配,如果最大匹配没有N个,那么就输出none。我们知道,如果一个信和信封是唯一对应的,那么删去这条边,将不存在完美匹配。所以我们对于每个信封,删去它与信封对应的边,看是否有完美匹配,如果没有就输出。注意最后要将边加上。


代码



function find(p:longint):longint;


var


? t,q:longint;


begin


? find:=true;


? t:=ls[p];


? while t>0 do


??? with g[t] do


????? begin


??????? if v[y]=0 then


????????? begin


??????????? v[y]:=1;


??????????? q:=link[y];


??????????? link[y]:=p;


??????????? if (q=0) or find(q) then exit;


? ? ? ? ? ? link[y]:=q;


????????? end;


??????? t:=next;


? ? ?end;


? find:=false;


end;


procedure match;


var


? i,ans:longint;


begin


?fillchar(link,sizeof(link),0);


?for i:=1 to n do


? ?begin


? ? ?fillchar(v,sizeof(v),0);


? ? ?if find(i)then ans:=ans+1;


? ?end;


?writeln(ans);


end;









友情链接: