fp一个匹配问题(匈牙利算法)John先生晚上写了n封信,并相应地写了n个信封将信装好,准备寄出.但是,第二天John的儿子Small John将这n封信都拿出了信封.不幸的是,Small John无法将拿出的信正确地
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/29 01:17:11
![fp一个匹配问题(匈牙利算法)John先生晚上写了n封信,并相应地写了n个信封将信装好,准备寄出.但是,第二天John的儿子Small John将这n封信都拿出了信封.不幸的是,Small John无法将拿出的信正确地](/uploads/image/z/12150607-31-7.jpg?t=fp%E4%B8%80%E4%B8%AA%E5%8C%B9%E9%85%8D%E9%97%AE%E9%A2%98%EF%BC%88%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95%EF%BC%89John%E5%85%88%E7%94%9F%E6%99%9A%E4%B8%8A%E5%86%99%E4%BA%86n%E5%B0%81%E4%BF%A1%2C%E5%B9%B6%E7%9B%B8%E5%BA%94%E5%9C%B0%E5%86%99%E4%BA%86n%E4%B8%AA%E4%BF%A1%E5%B0%81%E5%B0%86%E4%BF%A1%E8%A3%85%E5%A5%BD%2C%E5%87%86%E5%A4%87%E5%AF%84%E5%87%BA.%E4%BD%86%E6%98%AF%2C%E7%AC%AC%E4%BA%8C%E5%A4%A9John%E7%9A%84%E5%84%BF%E5%AD%90Small+John%E5%B0%86%E8%BF%99n%E5%B0%81%E4%BF%A1%E9%83%BD%E6%8B%BF%E5%87%BA%E4%BA%86%E4%BF%A1%E5%B0%81.%E4%B8%8D%E5%B9%B8%E7%9A%84%E6%98%AF%2CSmall+John%E6%97%A0%E6%B3%95%E5%B0%86%E6%8B%BF%E5%87%BA%E7%9A%84%E4%BF%A1%E6%AD%A3%E7%A1%AE%E5%9C%B0)
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.