[bzoj1059]矩陣游戲

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

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

（懶得寫鄰接表了~）

posted @ 2017-08-15 13:09 AristocratMarser 閱讀(240) 評論(0) 收藏舉報

刷新頁面返回頂部