首页 > 代码库 > ZJOI2007矩阵游戏

ZJOI2007矩阵游戏

2024-07-09 00:08:40   225人阅读

我们应该通过思考得到这样一个性质：如果一个点被选了，那么与它同行同列的点都不能选

然后就是裸的二分图匹配了……

（我应该能想出这道题来的，可是看了看题觉得没思路就去看题解了，唉……以后这种水题自己一定要动脑想想！）

代码：这种水题应该1A吧

 1 var i,j,n,t:longint; 2     flag:boolean; 3     p:array[0..250] of longint; 4     v:array[0..250] of boolean; 5     a:array[0..250,0..250] of longint; 6 function find(x:longint):boolean; 7  var i:longint; 8  begin 9   for i:=1 to n do10    if (not(v[i])) and (a[x,i]=1) then11      begin12        v[i]:=true;13        if (p[i]=0) or (find(p[i])) then14          begin15            p[i]:=x;16            exit(true);17          end;18      end;19   exit(false);20  end;21 procedure init;22  begin23    readln(n);24    fillchar(p,sizeof(p),0);25    for i:=1 to n do26     begin27       for j:=1 to n do read(a[i,j]);28       readln;29     end;30  end;31 procedure main;32  begin33    flag:=true;34    for i:=1 to n do35     begin36       fillchar(v,sizeof(v),false);37       if not(find(i)) then begin flag:=false;break;end;38     end;39    if flag then writeln(‘Yes‘) else writeln(‘No‘);40  end;41 42 begin43   readln(t);44   while t>0 do45    begin46      dec(t);47      init;48      main;49    end;50 end.
View Code

 

 


联系
我们