題干：

　　小Q是一個非常聰明的孩子，除了國際象棋，他還很喜歡玩一個電腦益智游戲——矩陣游戲。矩陣游戲在一個N

*N黑白方陣進(jìn)行（如同國際象棋一般，只是顏色是隨意的）。每次可以對該矩陣進(jì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

Hint

解題報告：

題目等價為“是否可以找出n個點使得兩兩不同行且兩兩不同列”或者說“找出n個點可以覆蓋到所有的行和所有的列”。不難證明這兩個命題是等價的，在這個二分圖中，每條邊代表一個點，每個點代表某一個行或者某一列，所以這就是個邊覆蓋問題，看能否覆蓋所有的點。我們直接看Yes的條件：也就是我們找到n個矩陣中的點（也就是二分圖中的邊），使得可以覆蓋所有二分圖的點，那么只有匹配數(shù)=n才可以做到。所以只要求個匹配就行了。連了一條邊，代表的含義就是這條邊連接的兩個點（也就是對應(yīng)的行和對應(yīng)的列）已經(jīng)被占用了，不能別人再來占用了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 200 + 5; int a[MAX][MAX],n; int used[MAX],nxt[MAX]; bool line[MAX][MAX]; bool find(int x) {for(int i = 1; i<=n; i++) {if(a[x][i] && used[i] == 0) {used[i] = 1;if(nxt[i] == 0 || find(nxt[i])) {nxt[i] = x;return 1;} } }return 0 ; } int match() {int res = 0;for(int i = 1; i<=n; i++) {memset(used,0,sizeof used);if(find(i)) res++;}return res; } int main() {int t;cin>>t;while(t--) {scanf("%d",&n);memset(nxt,0,sizeof nxt);for(int i = 1; i<=n; i++) {for(int j = 1; j<=n; j++) {scanf("%d",&a[i][j]);if(a[i][j]) line[j][i]=1;}}int ans = match();if(ans == n) printf("Yes\n");else printf("No\n");}return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【BZOJ - 1059】矩阵游戏（二分图匹配，建图，最小边覆盖）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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