社区讨论

80分,我的二分图匹配哪里有问题啊

P1402酒店之王参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi6gxsvj
此快照首次捕获于
2025/11/20 04:42
4 个月前
此快照最后确认于
2025/11/20 04:42
4 个月前
查看原帖
CPP
var
  n,p,q,i,j,m,ans:longint;
  like1,like2:array[0..500,0..500]of boolean;
  used1,used2:array[0..500]of boolean;
  match1,match2:array[0..500]of longint;
function found1(x:longint):boolean;
var i:longint;
begin
  for i:=1 to p do
    if like1[x,i] and not used1[i] then
      begin
        used1[i]:=true;
        if (match1[i]=0)or(found1(i)) then begin
                                             match1[i]:=x;
                                             exit(true);
                                           end;
      end;
  exit(false);
end;
function found2(x:longint):boolean;
var i:longint;
begin
  for i:=1 to q do
    if like2[x,i] and not used2[i] then
      begin
        used2[i]:=true;
        if (match2[i]=0)or(found2(i)) then begin
                                             match2[i]:=x;
                                             exit(true);
                                           end;
      end;
  exit(false);
end;
begin
  readln(n,p,q);
  for i:=1 to n do
    for j:=1 to p do begin read(m); like1[i,j]:=(m=1); end;
  for i:=1 to n do
    for j:=1 to q do begin read(m); like2[i,j]:=(m=1); end;
  ans:=0;
  for i:=1 to n do
  begin
    fillchar(used1,sizeof(used1),false);
    fillchar(used2,sizeof(used2),false);
    if found1(i) and found2(i) then inc(ans);
  end;
  writeln(ans);
end.

回复

2 条回复,欢迎继续交流。

正在加载回复...