[bzoj 1059] [ZJOI2007]矩阵游戏

n*n的01矩阵, 可以交换任意两行, 任意两列. 问是否可以通过一些操作, 使得方阵的主对角线上均为1. (T组数据, n≤200) 根据置换群的知识, 如果一个矩阵可以通过上述操作变成单位矩阵, 它必然是置换矩阵.

一个01方阵是置换矩阵的充要条件: 每行每列恰有一个1.

读题不仔细, 以为主对角线以外的地方得全是0, 于是就这么写了......

发现不对, 改成每行每列至少有一个1.

不妨认为最终主对角线上的那些1是黑色的, 其余的1是灰色的, 0是白色的. 那么, 原来的方阵中, 把黑色视为1, 灰色和白色视为0, 得到一个置换矩阵. 反之, 如果能对原来的矩阵适当地染色, 产生一个置换矩阵, 那么原矩阵能通过一些操作, 使得主对角线上都是1.

但是 "每行每列至少有一个1" 只是必要条件. 如下:

1 0 0
1 0 0
0 1 1

我在考虑有没有什么数学上的方法. 比如, 上面的例子中有相同的两行, 行列式等于0. 但下面的矩阵是一个反例:

1 1 0
1 1 0
0 1 1

去看题解.

二分图匹配?

根本没往这方面想......

如果原图中(i,j)为1, 就连一条从行i到列j的边 (邻接矩阵都给出来了-_-b). 把一些1染成黑色, 相当于行到列的一个匹配. 原问题回答Yes, 当且仅当该二分图有完美匹配.

图论建模技能有点弱啊......

const int N = 200;
int n, a[N][N], l[N];
bool match[N], vis[N];

bool dfs(int x)
{
	if (vis[x]) return false;
	vis[x] = true;
	rep (y, 0, n) if (a[x][y]) {
		if (l[y] == -1 || dfs(l[y])) {
			l[y] = x;
			return match[x] = true;
		}
	}
	return false;
}

bool check()
{
	fill_n(l, n, -1);
	fill_n(match, n, false);
	int cnt = 0;
	rep (i, 0, n)
		if (!match[i]) {
			fill_n(vis, n, false);
			cnt += dfs(i);
		}
	return cnt == n;
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		rep (i, 0, n) rep (j, 0, n) scanf("%d", &a[i][j]);
		puts(check() ? "Yes" : "No");
	}
	return 0;
}