查看原题请戳这里
首先，题目告诉我们有以下两种操作：
行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）
列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色
但是，实际上我们只需要进行其中的一种操作就可以了。即我们两种操作混着用其实是没有什么效果的，这一点后文会解释到。
假设我们只交换行，那么如果有一行是这样的：
$$0\ 1\ 0\ 0$$
那么很显然，这一列能且只能在第二行上。
再看一个例子：
$$0\ 1\ 1\ 0$$
我们发现，这一行既可以放到第二行，也可以放到第三行。
所以，如果第i行需要在第k列上的颜色为黑色（数字为1），那么我们就将i和k连一条边。注意，这一步看上去是行和列匹配，但实际上则是边和边进行匹配——第i条边可以放到第k条边的位置上。因为对于一个正方形，其左上-右下的对角线会经过第k条边的第k个位置。
然后我们就可以去跑二分图最大匹配，若匹配数等于边数，则有解，否则无解。
为什么只考虑一种操作就可以了呢？
![]()
如图，我们发现第3列没有黄格，第2列有2个黄格，但交换了第2、3列以后，第2列就没有黄格了。所以说，在进行一种操作的基础上，进行另一种操作无非是拆东墙，补西墙。
code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register
#define qwq printf("qwq\n");
using namespace std;
int read()
{
register int x = 0,f = 1;register char ch;
ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
return x * f;
}
int n,cnt,x,tot,T,d[100005];
int with[100005],pd[100005];
struct edge{
int next,to,from;
}e[200005];
void add(int x,int y)
{
e[++cnt].to = y;
e[cnt].from = x;
e[cnt].next = d[x];
d[x] = cnt;
}
int find(int u)
{
for(int i = d[u]; i; i = e[i].next)
{
int v = e[i].to;
if(!pd[v])
{
pd[v] = 1;
if(with[v] == 0 || find(with[v]))
{
with[v] = u;
return 1;
}
}
}
return 0;
}
void cl()
{
for(int i = 1; i <= cnt; i++) e[i].to = 0;
cnt = 0;
tot = 0;
memset(d,0,sizeof(d));
memset(with,0,sizeof(with));
}
int main()
{
T = read();
while(T--)
{
n = read();
cl();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
x = read();
if(x) add(i,j);
}
for(int i = 1; i <= n; i++)
{
memset(pd,0,sizeof(pd));
if(find(i)) tot++;
}
if(tot == n) printf("Yes\n");
else printf("No\n");
}
return 0;
}
|
