信与信封问题最大匹配

89 阅读 0 评论 59 点赞

我是靠谱客的博主感动导师，最近开发中收集的这篇文章主要介绍信与信封问题最大匹配，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意

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

分析

信和信封之间的关系，是一种一一对应的关系，这是因为一封信只能放到一个信封里，而一个信封也只能装一封信。而从信息学的角度来看，这种一一对应的关系，也可以看作是二分图的匹配关系。

这条边所代表的关系也是确定的。容易看出，当且仅当对于G的所有完美匹配M，都存在一条匹配边xiyj，则可以确定信i可以放到信封j中。

这样，我们就从匹配的角度建立了一个新的模型。那么，这个模型要如何求解呢？

我们当然不能枚举出G所有的完美匹配，然后再去求它们边的交集——这和搜索就没什么分别。在这里，我们需要对这个模型再做一个小小的转换：我们发现，条件“对于G的所有完美匹配M，都存在一条匹配边xiyj”，等价于“如果图G存在完美匹配，而删除图G中的一条边xiyj得到的图G’中却不存在完美匹配”。

实际上，我们可以先找到图G的一个完美匹配M，这样，删边就只需考虑匹配边了（因为删除非匹配边得到G’，M仍然是G’的完美匹配）。这样，只需删除n条边，时间复杂度就降到了O(n4)。

再进一步分析，删除一条边以后，没有必要重新找完美匹配，只需检查可不可以找到新的增广链就可以了。这样，时间复杂度就进一步降到了O(n3)。

打邻接矩阵好过邻接表

代码

var
  a:array[1..1000,1..1000] of boolean;
  v:array[1..30000] of boolean;
  st,ls:array[1..30000] of longint;
  i,j,k:longint;
  n,m,nm:longint;

function find(r:longint):boolean;
var
  i,j,k:longint;
begin
  find:=true;
  for i:=1 to n do
    begin
      if not v[i] and a[r,i]
        then
          begin
            k:=st[i]; st[i]:=r; v[i]:=true;
            if (k=0) or find(k) then exit;
            st[i]:=k;
          end;
    end;
  find:=false;
end;

procedure main;
var
  i,j,k:longint;
  z:boolean;
begin
  for i:=1 to n do
    begin
      fillchar(v,sizeof(v),0);
      z:=find(i);
    end;
end;

begin
  readln(n);
  readln(j,k);
  fillchar(a,sizeof(a),true);
  while j+k<>0 do
    begin
      a[k,j]:=false;
      readln(j,k);
    end;
  main;
  nm:=0;
  for i:=1 to n do
    begin
      k:=st[i]; st[i]:=0; a[k,i]:=false;
      fillchar(v,sizeof(v),0);
      if not find(k) then
        begin
          st[i]:=k;
          writeln(i,' ',k);
          nm:=1;
        end;
      a[k,i]:=true;
    end;
  if nm=0 then write('none');
end.