【BZOJ】1059: [ZJOI2007]矩阵游戏（二分图匹配）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

http://www.lydsy.com/JudgeOnline/problem.php?id=1059

本题可以看出，无论怎样变化，在同一行和同一列的数永远都不会分手～～～还是吐槽，，我第一眼yy了一个做法，就是直接判断读入的是否行或者列被占用了，如果没有，就累计，最后判断累计的数目是否为n即可。。。样例过啦～提交～。。wa了。。。

why？？不知道。。。自己测了几个样例都过了0.0，，，，先不管，，写个正解吧，，看了题解是二分图，每列都找一行，看看能否匹配，如果能匹配完，此题有解（显然的吧），写完后提交。。dear。。数组又闹了，，re。。改了改才a。

（水平太淡了）

恩，造数据对拍了下之前的程序，找到了反例。。（数据删了。。。），大概想到是因为即使我占用了本行，，但是我把这列占了T_T，所以可能我把一个能和本行另一个点兼容的点给覆盖了T_T。。好吧。

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define for1(i,a,n) for(i=a;i<=n;++i)
#define for2(i,a,n) for(i=a;i<n;++i)
#define for3(i,a,n) for(i=a;i>=n;--i)
#define for4(i,a,n) for(i=a;i>n;--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define read(a) a=getnum()
#define print(a) printf("%d", a)
inline int getnum() { int ret=0; char c; for(c=getchar(); c<'0' || c>'9'; c=getchar()); for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0'; return ret; }const int N=300, M=N*N;
int ihead[N], inext[M], from[M], to[M], cnt, ans;
int y[N+N];
bool visy[N+N];
inline void add(int u, int v) {
inext[++cnt]=ihead[u]; ihead[u]=cnt; from[cnt]=u; to[cnt]=v;
inext[++cnt]=ihead[v]; ihead[v]=cnt; from[cnt]=v; to[cnt]=u;
}bool ifind(int u) {
int v, i;
for(i=ihead[u]; i; i=inext[i]) if(!visy[v=to[i]]) {
visy[v]=true;
if(!y[v] || ifind(y[v])) {
y[v]=u;
return true;
}
}
return false;
}int main() {
int t; read(t);
int n, i, j, k;
while(t--) {
read(n);
ans=1;
CC(y, 0);
CC(ihead, 0);
for1(i, 1, n) for1(j, 1, n) {
read(k);
if(k) add(i, n+j);
}
for1(i, 1, n) {
CC(visy, 0);
if(!ifind(i)) { ans=0; break; }
}
if(ans) printf("Yes\n");
else printf("No\n");
}
return 0;
}

Description

小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）列交换操作：选择矩阵的任意行列，交换这两列（即交换对应格子的颜色）游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。对于某些关卡，小Q百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！！于是小Q决定写一个程序来判断这些关卡是否有解。