首页 > 代码库 > CODEVS1222 信与信封问题 (匈牙利算法)

CODEVS1222 信与信封问题 (匈牙利算法)

先做一遍匈牙利算法。对于已经匹配的边,如果删去之后还能最大匹配数增加,则不符合要求。

一遍匈牙利算法是O(n^3)的,对于每一条边做n次,每次O(n^2),总的复杂度是O(n^3)。

注意:不要忘记输出none。

 1 var a:array[0..1000,0..1000] of boolean; 2     l,r:array[0..1000] of longint; 3     pd:array[0..1000] of boolean; 4     i,j,x,y,n,sum,num:longint; 5 function find(i:longint):boolean; 6 var j:longint; 7 begin 8     for j:=1 to n do 9         if a[i,j] and not pd[j] then10         begin11             pd[j]:=true;12             if (l[j]=0) or find(l[j]) then13             begin14                 l[j]:=i;15                 r[i]:=j;16                 exit(true);                17             end;18         end;19     exit(false);20 end;21 begin22     fillchar(a,sizeof(a),true);23     readln(n);24     readln(x,y);25     while not ((x=0) and (y=0)) do26     begin27         a[x,y]:=false;28         readln(x,y);29     end;30     fillchar(l,sizeof(l),0);31     fillchar(r,sizeof(r),0);32     sum:=0;33     for i:=1 to n do34     begin35         fillchar(pd,sizeof(pd),false);36         if find(i) then inc(sum);37     end;38     num:=0;39     for i:=1 to n do40     begin41         fillchar(pd,sizeof(pd),false);42                 j:=r[i];43         a[i,j]:=false;44         r[i]:=0; l[j]:=0;45         if not find(i) then begin inc(num); writeln(i, ,j); end;46         a[i,j]:=true;47         r[i]:=j; l[j]:=i;48     end;    49     if num=0 then writeln(none);50 end.

 

CODEVS1222 信与信封问题 (匈牙利算法)