(ssl1331)信与信封问题

2024-01-30 05:58

文章标签 问题信封 ssl1331

本文主要是介绍(ssl1331)信与信封问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

信与信封问题

Description

　　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，尽可能多地将信正确地装回信封。

Input

第一行是一个整数n（n≤100）。信和信封依次编号为1，2，…，n。
接下来的各行中每行有2个数i和j，表示第i封信肯定不是装在第j个信封中。文件最后一行是2个0，表示结束。

Output

输出的各行中每行有2个数i和j，表示第i封信肯定是装在第j个信封中。请按信的编号i从小到大顺序输出。若不能确定正确装入信封的任何信件，则输出“none”。

Sample Input

3
1 2
1 3
2 1
0 0
Sample Output

1 1

Hint

03年福建省赛

Source

ebla

题解：本题依旧是最大匹配(模板详见：这里)
本题的思路是先用匈牙利算法得出最大匹配，再通过删除路来寻找完美匹配。如果一条都没有的话就输出”none”。

vara:array[1..100,1..100]of boolean;v:array[1..100]of boolean;l:array[1..100]of longint;n,x,y,t,i,j:longint;f:boolean;
function try(i:longint):boolean;//匈牙利算法
varj,t:longint;
begintry:=true;for j:=1 to n doif not a[i,j] and not v[j] thenbegint:=l[j]; l[j]:=i; v[j]:=true;if (t=0) or try(t)then exit;l[j]:=t;end;try:=false;
end;
beginreadln(n);while 9=9 dobeginreadln(x,y);if x+y=0 then break;a[y,x]:=true;//断路end;for i:=1 to n dobeginfillchar(v,sizeof(v),0);try(i);end;for j:=1 to n dobegini:=l[j]; l[j]:=0; a[i,j]:=true;//删路前记得保存，后面需要还原fillchar(v,sizeof(v),0);if not try(i) then//存在就输出beginl[j]:=i;writeln(j,' ',i);//由于是从小到大枚举，所以能保证从小到大输出f:=true;//至少有一封信放进去了end;a[i,j]:=false;//还原end;if not f then writeln('none');//没有就输出"none"
end.