來源：牛客網(wǎng)：

題目描述

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

輸入描述:

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

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

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

輸出
復(fù)制

No Yes

說明
【數(shù)據(jù)規(guī)模】
對于100%的數(shù)據(jù)，N ≤ 200

題解：

根據(jù)題意我們可以這么想：無論怎么換行換列，同一行列的相對關(guān)系沒有發(fā)生改變，我們要找的n個不同行不同列的點(diǎn)，如果有一個1，那我們就將這個1的橫坐標(biāo)與縱坐標(biāo)連起來
例如：
1 0 1
1 1 0
0 1 1

我們構(gòu)造出這樣的圖，然后跑二分圖匹配就可以，如果可以全部匹配就輸出yes，否則就no

代碼：

#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int MAXN=40010,MAXM=1000010; struct Edge{int from,to,nxt; }e[MAXM]; int head[MAXN],edgeCnt=1; void addEdge(int u,int v){e[++edgeCnt].from=u;e[edgeCnt].to=v;e[edgeCnt].nxt=head[u];head[u]=edgeCnt; } bool vis[MAXN]; int match[MAXN]; bool dfs(int x){for(int i=head[x];i;i=e[i].nxt){int nowV=e[i].to;if(vis[nowV])continue;vis[nowV]=1;if(!match[nowV]||dfs(match[nowV])){match[nowV]=x;return 1;}}return 0; } void init(){memset(match,0,sizeof(match));memset(e,0,sizeof(e));edgeCnt=1;memset(head,0,sizeof(head)); } int main(){int t;scanf("%d",&t);while(t--){init();int n;scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){int tmp;scanf("%d",&tmp);if(tmp)addEdge(i,j);}int ans=0;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(dfs(i))ans++;}if(ans>=n)printf("Yes\n");else printf("No\n");}return 0; }

總結(jié)

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

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