Problem Specification Value
Time Limit 10 Sec
Memory Limit 162 MB
Submit 3604
Solved 1729

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

HINT

Source

交换任意两列、两行不会改变最终的结果, 黑白位置对应的排布也不会变化.

所以我们可以建一个二分图, 然后把被染黑的点的横纵坐标连在一起, 二分图匹配一下就可以了.


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
const int maxn = 210, maxm = 40010;

class Dinic
{
public:
    struct edge
    {
        int u, v;
        edge *next;
    };
    edge *edges[maxn], epool[maxm];
    int n, cnt, from[maxn], used[maxn];
    void addedge(int u, int v)
    {
        edge *p = &epool[cnt++];
        p->u = u; p->v = v;
        p->next = edges[u]; edges[u] = p;
        return ;
    }
    bool match(int p)
    {
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (!used[ep->v]) {
                used[ep->v] = true;
                if (!from[ep->v] || match(from[ep->v])) {
                    from[ep->v] = p;
                    return true;
                }
            }
        return false;
    }
    int eval(void)
    {
        memset(from, 0, sizeof(from));
        int res = 0;
        for (int i = 1; i <= n; i++) {
            memset(used, 0, sizeof(used));
            if (match(i))
                res++;
        }
        return res;
    }
    void reset(int n_)
    {
        n = n_;
        memset(edges, 0, sizeof(edges));
        cnt = 0;
        return ;
    }
} graph;

int n, T;

int main(int argc, char** argv)
{
    scanf("%d", &T);
    for (int idx = 1; idx <= T; idx++) {
        scanf("%d", &n);
        graph.reset(n);
        int tot = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1, a; j <= n; j++) {
                scanf("%d", &a);
                if (a > 0) {
                    tot++;
                    graph.addedge(i, j);
                }
            }
        int res = graph.eval();
        printf("%s\n", res >= n ? "Yes" : "No");
    }
    return 0;
}
from pydatagen import *
T = randrange(1, 10)
printf("%d\n", T)
for i in range(0, T):
    n = randrange(10, 200)
    printf("%d\n", n)
    for j in range(0, n):
        for k in range(0, n):
            if possibility(2.0 / n):
                printf("1 ")
            else:
                printf("0 ")
        printf("\n")
    pass