首页 > 代码库 > 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 信与信封问题 (匈牙利算法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。