bzoj 1059: [ZJOI2007]矩阵游戏 (匈牙利算法)

1059: [ZJOI2007]矩阵游戏

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 5251  Solved: 2512
[Submit][Status][Discuss]

Description

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

Input

  第一行包含一个整数T,表示数据的组数。接下来包含T组数据,每组数据第一行为一个整数N,表示方阵的大
小;接下来N行为一个N*N的01矩阵(0表示白色,1表示黑色)。

Output

  输出文件应包含T行。对于每一组数据,如果该关卡有解,输出一行Yes;否则输出一行No。

Sample Input

2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0

Sample Output

No
Yes
【数据规模】
对于100%的数据,N ≤ 200
思路:
纠结了一下建图,由于每个黑点可以按照行换,也可以按照列换。所以我建了一个1..n到1..2n的二分图做匹配。
左边集合是n个对角线上的点,右边集合是行号+列号。
但是每次匹配的时候,一个对角线上的点会同时消耗到匹配的行号和列号。。感觉不是很对啊。。。
实际上发现,我们只需要建立一个n到n的二分图就行了。
原因是,如果有解,那么只需要行或者列的一种变换,就可以达到规定的图案。
比如现在(2,5)是1,(2,2)和(5,5)是0,我们只需要连一条边表示(2,5)可以换到(2,2)即可,不需要连表示(2,5)可以换到(5,5)的边
原因是,如果(2,5)换到(5,5),那么(2,2)也跟着换到了(5,2),我们不考虑之前的(2,2)是什么,被换之后的(2,2)必须是1才符合题意,也就是换之前的(5,2)必须是1.
既然(5,2)是1,那么从(5,2)换到(5,5)即可符合条件。

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz