fp一个匹配问题（匈牙利算法）John先生晚上写了n封信,并相应地写了n个信封将信装好,准备寄出.但是,第二天John的儿子Small John将这n封信都拿出了信封.不幸的是,Small John无法将拿出的信正确地
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/16 22:23:57
fp一个匹配问题（匈牙利算法）John先生晚上写了n封信,并相应地写了n个信封将信装好,准备寄出.但是,第二天John的儿子Small John将这n封信都拿出了信封.不幸的是,Small John无法将拿出的信正确地
fp一个匹配问题（匈牙利算法）
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,尽可能多地将信正确地装回信封.
è数据输入：
输入数据由文件名为foi.in的文本文件提供.
n文件的第一行是一个整数n（n≤100）.信和信封依次编号为1,2,…,n.
n接下来的各行中每行有2个数i和j,表示第i封信肯定不是装在第j个信封中.文件最后一行是2个0,表示结束.
结果输出:
计算结果输出到文件名为foi.out 的文本文件中.
输出文件的各行中每行有2个数i和j,表示第i封信肯定是装在第j个信封中.请按信的编号i从小到大顺序输出.若不能确定正确装入信封的任何信件,则输出“none”.
输入示例
5
1 2
1 4
1 5
2 1
2 3
3 2
3 5
4 1
4 3
5 2
5 4
5 5
0 0
输出示例
3 4
fp一个匹配问题（匈牙利算法）John先生晚上写了n封信,并相应地写了n个信封将信装好,准备寄出.但是,第二天John的儿子Small John将这n封信都拿出了信封.不幸的是,Small John无法将拿出的信正确地
program p1557;
var
i,j,m,n,x,y,tot,v:longint;
link:array[1..200] of longint;
cover,f:array[1..200] of boolean;
map:array[0..200,0..200] of boolean;
Function work(i:longint):boolean;
var
q,k:longint;
begin
work:=true;
for k:=1 to n do
if (map[i,k]=true) and (cover[k]=false) then
begin
q:=link[k];
link[k]:=i;
cover[k]:=true;
if (q=0) or (work(q)=true) then exit;
link[k]:=q;
end;
work:=false;
end;
Begin
assign(input,'i.i'); reset(input);
assign(output,'o.o'); rewrite(output);
readln(n);
for i:=1 to n do
for j:=1 to n do
map[i,j]:=true;
repeat
readln(x,y);
map[y,x]:=false;
until (x=0) and (y=0);
for i:=1 to n do
begin
for j:=1 to n do
cover[j]:=false;
work(i);
end;
tot:=0;
for i:=1 to n do
begin
j:=link[i];
link[i]:=0;
map[j,i]:=false;
for v:=1 to n do cover[v]:=false;
if (work(j)=false) then
begin
tot:=tot+1;
writeln(j,' ',i);
end;
map[j,i]:=true;
link[i]:=j;
end;
if tot=0 then writeln('none')
end.