Description
给你一个01矩阵，你每次操作可以交换两行或者交换两列。
问你是否能得到一个矩阵使得矩阵的主对角线（左上角到右下角的连线）都为1。
Solution
这是一道[ZJOI2007]的题。
因为同行同列的点，变化后仍然是同行同列的。
因为对角线都是不同行不同列的，所以我们只要找不同行同列的是否到了n个就可以了。
如果原矩阵中第i行第j列为1，那么就Xi -> Yj连一条边。然后跑最大匹配即可。
Notice
因为有多组数据，千万要记得每次对match数组清零。
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
87
88
using namespace std;
const ll INF = 1e9, Mo = 998244353;
const int N = 200;
const double eps = 1e-6;
namespace slow_IO
{
ll read()
{
ll x = 0; int zf = 1; char ch = getchar();
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') zf = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * zf;
}
void write(ll y)
{
if (y < 0) putchar('-'), y = -y;
if (y > 9) write(y / 10);
putchar(y % 10 + '0');
}
}
using namespace slow_IO;
int head[N + 5], vis[N + 5], match[N + 5];
int edgenum = 0;
struct node
{
int vet, next;
}edge[N * N + 5];
void addedge(int u, int v)
{
edge[edgenum].vet = v;
edge[edgenum].next = head[u];
head[u] = edgenum++;
}
int Find(int u)
{
travel(i, u)
{
int v = edge[i].vet;
if (vis[v]) continue;
vis[v] = 1;
if (!match[v] || Find(match[v]))
{
match[v] = u;
return 1;
}
}
return 0;
}
int sqz()
{
int H_H = read();
while (H_H--)
{
int n = read();
int ans = 0; edgenum = 0;
rep(i, 1, n) head[i] = -1, match[i] = 0;
rep(i, 1, n)
rep(j, 1, n)
{
int x = read();
if (x) addedge(i, j);
}
rep(i, 1, n)
{
rep(j, 1, n) vis[j] = 0;
if (Find(i)) ans++;
}
if (ans == n) puts("Yes");
else puts("No");
}
return 0;
}
Hopcroft-Karp算法版本：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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
using namespace std;
const ll INF = 1e9, Mo = 998244353;
const int N = 200;
const double eps = 1e-6;
namespace slow_IO
{
ll read()
{
ll x = 0; int zf = 1; char ch = getchar();
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') zf = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * zf;
}
void write(ll y)
{
if (y < 0) putchar('-'), y = -y;
if (y > 9) write(y / 10);
putchar(y % 10 + '0');
}
}
using namespace slow_IO;
int head[N + 5], vis[N + 5], Matchx[N + 5], Matchy[N + 5], Disx[N + 5], Disy[N + 5];
int edgenum = 0, n, Dis;
struct node
{
int vet, next;
}edge[N * N + 5];
void addedge(int u, int v)
{
edge[edgenum].vet = v;
edge[edgenum].next = head[u];
head[u] = edgenum++;
}
queue<int> Q;
int bfs()
{
rep(i, 1, n)
{
Disx[i] = Disy[i] = -1;
if (!Matchx[i]) Q.push(i), Disx[i] = 0;
}
Dis = INF;
while (!Q.empty())
{
int u = Q.front(); Q.pop();
if (Disx[u] > Dis) continue;
travel(i, u)
{
int v = edge[i].vet;
if (~Disy[v]) continue;
Disy[v] = Disx[u] + 1;
if (!Matchy[v]) Dis = Disy[v];
else
{
Disx[Matchy[v]] = Disy[v] + 1;
Q.push(Matchy[v]);
}
}
}
return Dis != INF;
}
int dfs(int u)
{
travel(i, u)
{
int v = edge[i].vet;
if (!vis[v] && Disy[v] == Disx[u] + 1)
{
vis[v] = 1;
if (!Matchy[v] || dfs(Matchy[v]))
{
Matchy[v] = u, Matchx[u] = v;
return 1;
}
}
}
return 0;
}
int MaxMatch()
{
int Match = 0;
while (bfs())
{
rep(i, 1, n) vis[i] = 0;
rep(i, 1, n) if (!Matchx[i]) Match += dfs(i);
}
return Match;
}
int sqz()
{
int H_H = read();
while (H_H--)
{
n = read();
int ans = 0; edgenum = 0;
rep(i, 1, n) head[i] = -1, Matchx[i] = Matchy[i] = 0;
rep(i, 1, n)
rep(j, 1, n)
{
int x = read();
if (x) addedge(i, j);
}
if (MaxMatch() == n) puts("Yes");
else puts("No");
}
return 0;
}