首页 > 代码库 > WIKIOI 1222信与信封问题

WIKIOI 1222信与信封问题

2024-07-12 15:33:05   220人阅读

题目描述 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 Description

n文件的第一行是一个整数n（n≤100）。信和信封依次编号为1，2，…，n。

n接下来的各行中每行有2个数i和j，表示第i封信肯定不是装在第j个信封中。文件最后一行是2个0，表示结束。

输出描述 Output Description

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

样例输入 Sample Input

3

1  2

1  3

2  1

0  0

样例输出 Sample Output

1   1

数据范围及提示 Data Size & Hint

题解：（摘抄）

典型的二分图最大匹配匈牙利算法

若完美匹配中一条边必须存在, 那如果删掉这条边就不会存在完美匹配

代码:

 1 var px,py:array[0..100] of longint; 2     map:array[0..100,0..100] of boolean; 3     i,n,op,t,x,y,ans:longint; 4     vis:array[0..100] of longint; 5     flag:boolean; 6 function find(x:longint):boolean; 7   var i:longint; 8   begin 9   for i:=1 to n do10    if map[x,i] then11     begin12      if (vis[i]=t) then continue;13      vis[i]:=t;14      if (py[i]=0) or (find(py[i])) then15       begin16        py[i]:=x;17        px[x]:=i;18        exit(true);19       end;20     end;21    exit(false);22   end;23 procedure init;24  begin25  readln(n);26  readln(x,y);27  fillchar(map,sizeof(map),true);28  while (x<>0) and (y<>0) do29   begin30   map[x,y]:=false;31   readln(x,y);32   end;33  end;34 procedure main;35  begin36  for i:=1 to n do37   begin38   t:=i;39   if (find(i)) then inc(ans);40   end;41  if ans<>n then writeln(‘none‘)42  else43   begin44    flag:=false;45    fillchar(vis,sizeof(vis),0);46    for i:=1 to n do47     begin48      t:=i;49      op:=px[i];50      map[i,op]:=false;51      py[op]:=0;px[i]:=0;52      if not(find(i)) then53       begin54        writeln(i,‘ ‘,op);55        px[i]:=op;56        py[op]:=i;57        flag:=true;58        end;59      map[i,op]:=true;60      end;61    if not(flag) then writeln(‘none‘);62   end;63  end;64 begin65  init;66  main;67 end.
View Code

 


联系
我们