首页 > 代码库 > 1059: [ZJOI2007]矩阵游戏

1059: [ZJOI2007]矩阵游戏

2024-08-09 00:08:38   218人阅读

1059: [ZJOI2007]矩阵游戏

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2154  Solved: 1053
[Submit][Status]

Description

小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）列交换操作：选择矩阵的任意行列，交换这两列（即交换对应格子的颜色）游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。对于某些关卡，小Q百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！！于是小Q决定写一个程序来判断这些关卡是否有解。

Input

第一行包含一个整数T，表示数据的组数。接下来包含T组数据，每组数据第一行为一个整数N，表示方阵的大小；接下来N行为一个N*N的01矩阵（0表示白色，1表示黑色）。

Output

输出文件应包含T行。对于每一组数据，如果该关卡有解，输出一行Yes；否则输出一行No。

Sample Input

2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0

Sample Output

No
Yes
【数据规模】
对于100%的数据，N ≤ 200

HINT

 

Source

 

 题解：额。。。这辈子第一道成功的真正意义上的网络流题（phile：今儿咋和这辈子干上了？ HansBug：讨厌啦*^_T*），这个题由于到处都是行交换列交换，所以弄来弄去所有“1”点的横坐标还是那么几个数，纵坐标也是，所以问题就成了从所有的黑格子中选N个出来，且横纵坐标各不同，所以可以进行NetWorkFlow建模——将横坐标1-N建立为2-(N+1)，纵坐标建立为(n+2)-(2*n+1)，源点为1，汇点为(2*n+2)，对于棋盘中的黑点(x,y),则在网络图中，(n+x)-(n+1+y)有一条边权为1的有向边，然后源点到各个横坐标点各连一个如上的边，各个纵坐标点到汇点也是，然后求网络流就是啦（这种将点分为两个点集然后求匹配的叫做二分图匹配，也可以用匈牙利算法做，且更好，可惜我不会TT），只要最大流=N则说明可以办到，否则不能，That‘s all......（只用了个GAP优化连邻接表都没用的SAP居然612ms我也是醉了*_*）
 
 1 var 2    i,j,k,l,m,n,aug,jl,mi,tmp,ans,vi,vx:longint; 3    flag:boolean; 4    a:array[0..500,0..500] of longint; 5    di,dis,his,pre,vh:array[0..1000] of longint; 6 function max(x,y:longint):longint; 7          begin 8               if x>y then max:=x else max:=y; 9          end;10 function min(x,y:longint):longint;11          begin12               if x<y then min:=x else min:=y;13          end;14 begin15      readln(vx);16      for vi:=1 to vx do17          begin18 19      readln(n);20      fillchar(a,sizeof(a),0);21      for i:=1 to n do22          begin23               a[1,i+1]:=1;24               a[n+1+i,n*2+2]:=1;25          end;26      for i:=1 to n do27          begin28               for j:=1 to n do29                   begin30                        read(k);31                        a[1+i,n+1+j]:=k;32                   end;33               readln;34          end;35      fillchar(dis,sizeof(dis),0);36      fillchar(his,sizeof(his),0);37      fillchar(vh,sizeof(vh),0);38      for i:=1 to n*2+2 do39          di[i]:=1;40      vh[0]:=n*2+2;41      aug:=maxlongint;42      i:=1;ans:=0;43      while dis[1]<(n*2+2) do44            begin45                 flag:=false;46                 his[i]:=aug;47                 for j:=di[i] to n*2+2 do48                     begin49                          if (a[i,j]>0) and ((dis[i]-1)=dis[j]) then50                             begin51                                  aug:=min(aug,a[i,j]);52                                  pre[j]:=i;53                                  di[i]:=j;54                                  i:=j;55                                  if i=(2*n+2) then56                                     begin57                                          ans:=ans+aug;58                                          while i<>1 do59                                                begin60                                                     tmp:=i;61                                                     i:=pre[i];62                                                     a[i,tmp]:=a[i,tmp]-aug;63                                                     a[tmp,i]:=a[i,tmp]+aug;64                                                end;65                                          aug:=maxlongint;66                                     end;67                                  flag:=true;68                                  break;69 70                             end;71                     end;72                 if flag then continue;73                 jl:=-1;mi:=2*n+1;74                 for j:=1 to 2*n+2 do75                     begin76                          if (dis[j]<mi) and (a[i,j]>0) then77                             begin78                                  mi:=dis[j];79                                  jl:=j;80                             end;81                     end;82                 di[i]:=jl;83                 dec(vh[dis[i]]);84                 if vh[dis[i]]<=0 then break;85                 dis[i]:=mi+1;86                 inc(vh[dis[i]]);87                 if i<>1 then88                    begin89                         i:=pre[i];90                         aug:=his[i];91                    end;92            end;93      if ans=n then writeln(‘Yes‘) else writeln(‘No‘);94 95          end;96 end.97

 

1059: [ZJOI2007]矩阵游戏


联系
我们