[bzoj1059]矩陣游戲

雖然是一道水難題，但是我這種蒟蒻還是要講一講的。

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

題解：顯然模擬可知，在同一行或同一列的格子，無論如何移動都會保持在同一行（列），所以可以直接以行和列建圖，如果ai,j=1，就由i向j連一條邊。

顯然這是一個二分圖，直接套匈牙利即可。

代碼：

#include<cstdio>
#include<cstring>
#define r register
bool a[205][205],vis[405];
int linked[405];
int n,T;
bool match(int u){  for(r int i=1;i<=n;i++){if(!a[u][i]||vis[i])continue;vis[i]=1;if(linked[i]<0||match(linked[i])){linked[i]=u;return 1;}}return 0; 
}
int main(){scanf("%d",&T);while(T--){scanf("%d",&n);for(r int i=1;i<=n;i++)for(r int j=1;j<=n;j++)scanf("%d",&a[i][j]);memset(linked,-1,sizeof linked);r int ans=0;for(r int i=1;i<=n;i++){memset(vis,0,sizeof(vis));ans+=match(i);}puts(ans==n?"Yes":"No");}return 0;
}

（懶得寫鄰接表了~）