P1129 [ZJOI2007]矩陣游戲

題目描述

小\(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\)表示黑色）。

輸出格式：

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

說明

對于\(20\)%的數(shù)據(jù)，\(N ≤ 7\)

對于\(50\)%的數(shù)據(jù)，\(N ≤ 50\)

對于\(100\)%的數(shù)據(jù)，\(N ≤ 200\)

---

研究一下操作和要求，我們可以這么轉(zhuǎn)化：每行至少有一個\(1\)并且這些\(1\)互相不在同一列

對于行\(i\),我們用了坐標(biāo)\((i,j)\)的\(1\)，那么第\(j\)列的\(1\)不就廢了嗎？

好的，求匹配。

坐標(biāo)為\((i,j)\)的點(diǎn)作為第\(i\)行第\(j\)列的邊。

求每一行和每一列的最大匹配數(shù)即可。

二分圖匹配。

---

code：

#include <cstdio> #include <cstring> const int N=202; struct Edge {int to,next; }g[N*N]; int T,head[N],cnt=0,n;void add(int u,int v) {g[++cnt].to=v,g[cnt].next=head[u],head[u]=cnt; } int match[N],used[N]; bool m_match(int now) {for(int i=head[now];i;i=g[i].next){int v=g[i].to;if(!used[v]){used[v]=1;if(!match[v]||m_match(match[v])){match[v]=now;return true;}}}return false; }int main() {scanf("%d",&T);int is;while(T--){memset(match,0,sizeof(match));memset(head,0,sizeof(head));scanf("%d",&n);cnt=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){scanf("%d",&is);if(is) add(i,j);}int ans=0;for(int i=1;i<=n;i++){memset(used,0,sizeof(used));if(m_match(i)) ans++;}if(ans==n) printf("Yes\n");else printf("No\n");} }

---

我的一些出現(xiàn)的細(xì)節(jié)錯誤：

匈牙利used數(shù)組置true時機(jī)(似乎經(jīng)常錯)

used置0的時機(jī)(在if的外面)

前向星head,cnt置0

---

2018.5.5

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

總結(jié)

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

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