匹配算法

二分图最大基数匹配

二分图最大基数匹配的算法是匈牙利算法和Hopcroft Karp算法.

 var
  map:array[1..100,1..100] of boolean; {保存二分图}
  cover:array[1 .. 100] of boolean; {标记一个点是否为饱和点}
  link:array[1 .. 100] of integer; {保存匹配边}
  n,i,e,x,y,s:integer;
 procedure init; {读入}
 begin
  readln(n, e);
  for i:=1 to e do 
   begin
    readln(x,y); 
    map[x,y]:=true;
   end;
 end;
 function find(i:integer):boolean; {从i出发，找增广链}
 var
  k,q:integer;
 begin
  for k:=1 to n do
    if map[i,k] and not cover[k] then 
     begin
      q:=link[k]; link[k]:=i; cover[k]:=true;{假设可以连到k上取代原来的连接}
      if (q=0)or(find(q)) then exit(true);{如果可以找到就直接退出}
      link[k]:=q;{找不到，把值改回}
     end;
  exit(false);
 end;
 procedure main; {求匹配}
 begin
  for i:=1 to n do 
   begin
     fillchar(cover,sizeof(cover),0);
     find(i);｛对每个点找匹配｝
   end;
 end;
 procedure print; {输出}
 begin
  s:=0; 
  for i := 1 to n do 
     if link[i]<>0 then s:=s+1;
    writeln(s);
  for i:=1 to n do if link[i]<>0 then 
    writeln(link[i],' ',i);
 end;
 begin
  init;
  main;
  print;
 end.

二分图最大权匹配

目前通行的算法是[[KM算法]

 function find(k:longint):longint;
  var i:longint;
 begin
  x[k]:=true;
  for i:=1 to n do 
    if (not y[i]) and (lx[k]+ly[i]=g[k,i]) then
	  begin
	    y[i]:=true;
		if link[i]=0 then
		  begin
		    link[i]:=k;
            exit(true);
		  end
		else if find(link[i]) then
          begin
 		    link[i]:=k;
			exit(true);
          end;
      end;
   exit(false);	  
  end;
 procedure km;
  var i,j,k,d:longint;
 begin
  fillchar(lx,sizeof(lx),0);
  fillchar(ly,sizeof(ly),0);
  for i:=1 to n do
    for j:=1 to n do 
	  if g[i,j]>lx[i] then
	    lx[i]:=g[i,j];
  for k:=1 to n do 
    repeat
	  fillchar(x,sizeof(x),0);
	  fillchar(y,sizeof(y),0);
	  if find(k) then break;
	  d:=maxlongint;
	  for i:=1 to n do 
	    if x[i] then
		  for j:=1 to n do 
		    if not y[j] then
			  if lx[i]+ly[j]<d then
			    d:=lx[i]+ly[j];
	  for i:=1 to n do
	    begin
		  if x[i] then dec(lx[i],d);
		  if y[i] then inc(ly[i],d);
		end;
	until false;
  end;