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

Description

小Q是一個非常聰明的孩子，除了國際象棋，他還很喜歡玩一個電腦益智游戲——矩陣游戲。矩陣游戲在一個N *N黑白方陣進行（如同國際象棋一般，只是顏色是隨意的）。每次可以對該矩陣進行兩種操作：行交換操作：選擇 矩陣的任意兩行，交換這兩行（即交換對應(yīng)格子的顏色）列交換操作：選擇矩陣的任意行列，交換這兩列（即交換 對應(yīng)格子的顏色）游戲的目標(biāo)，即通過若干次操作，使得方陣的主對角線(左上角到右下角的連線)上的格子均為黑 色。對于某些關(guān)卡，小Q百思不得其解，以致他開始懷疑這些關(guān)卡是不是根本就是無解的！！于是小Q決定寫一個程 序來判斷這些關(guān)卡是否有解。

Input

第一行包含一個整數(shù)T，表示數(shù)據(jù)的組數(shù)。接下來包含T組數(shù)據(jù)，每組數(shù)據(jù)第一行為一個整數(shù)N，表示方陣的大 小；接下來N行為一個N*N的01矩陣（0表示白色，1表示黑色）。

Output

　　輸出文件應(yīng)包含T行。對于每一組數(shù)據(jù)，如果該關(guān)卡有解，輸出一行Yes；否則輸出一行No。

Sample Input

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

Sample Output

No
Yes
【數(shù)據(jù)規(guī)模】
對于100%的數(shù)據(jù)，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; } View Code

（懶得寫鄰接表了~）

轉(zhuǎn)載于:https://www.cnblogs.com/Marser/p/7364573.html

總結(jié)

以上是生活随笔為你收集整理的[bzoj1059]矩阵游戏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。