POJ 3692（匈牙利算法）

匈牙利算法：

b[]保存当前找交错路P的各点是否已被连通，a[]表示某点之前的点

本题的2分图是取最大团（各点互相连通），利用2分图性质，可看成补图的最大独立集（各点互不连通）……

Program P3692;
const
   maxn=200;

var
   n,m,l,i,j,k,ans,x,y:longint;
   b:array[1..400] of boolean;
   map:array[1..400,1..400] of boolean;
   a:array[1..400] of longint;
function find(x:longint):boolean;
var
   i,j:longint;
begin
   for i:=1 to m do
      if not(b[i]) and (map[x,i]) then
      begin
         b[i]:=true;
         if a[i]=0 then begin a[i]:=x; exit(true); end;
         if find(a[i]) then begin a[i]:=x; exit(true); end;
      end;

   exit(false);
end;
begin
   i:=1;
   read(n,m,l);
   while (n+m+l>0) do
   begin
      ans:=0;
      fillchar(a,sizeof(a),0);
      fillchar(map,sizeof(map),true);
      for k:=1 to l do
      begin
         read(x,y);
         map[x,y]:=false;
      end;
      for k:=1 to n do
      begin
         fillchar(b,sizeof(b),false);
         if find(k) then inc(ans);
      end;
      writeln('Case ',i,': ',n+m-ans);
      inc(i);
      read(n,m,l);
   end;
end.