[ZJOI2007] 矩阵游戏

题意

给定一个 n x n 的 01 矩阵，其中 1 表示黑格，0 表示白格。

你可以进行两种操作：

交换任意两行
交换任意两列

问能否经过若干次操作后，让主对角线上的 n 个位置全部变成黑格。

思路

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;

int T;
int n;
int a[MAXN][MAXN];
int used_col[MAXN];

// 朴素搜索：按行依次决定，这一行到底选哪一列的黑格。
// 只要能给每一行都选到一个互不冲突的黑格，就说明答案是 Yes。
bool dfs(int row) {
    if (row > n) {
        return true;
    }

    for (int col = 1; col <= n; col++) {
        if (a[row][col] == 0 || used_col[col]) {
            continue;
        }
        used_col[col] = 1;
        if (dfs(row + 1)) {
            return true;
        }
        used_col[col] = 0;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> a[i][j];
            }
        }

        memset(used_col, 0, sizeof(used_col));
        if (dfs(1)) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}

brute.cpp 按行依次选择黑格，并保证列不重复。
只要能给每一行都选到一个互不冲突的列，就说明存在一组黑格能放上主对角线。

这个暴力已经抓住了题目的本质，但它还是回溯搜索，数据一大就会超时。

真正的关键是看清“交换”到底改变了什么。

一个黑格原来在第 i 行、第 j 列。无论怎么交换：

它始终属于“原来的第 i 行”
也始终属于“原来的第 j 列”

交换操作只是在重新排列行和列的顺序，并不会创造新的“行和列的可配对关系”。

所以题目其实是在问：

能不能从矩阵里选出 n 个黑格
它们两两不在同一行，也不在同一列

一旦能选出这 n 个黑格，就可以把对应的行和列重新排列，把它们送到主对角线上。

这时模型就非常明显了：

左边放 n 个“行”
右边放 n 个“列”
如果 a[i][j] = 1，就在第 i 行和第 j 列之间连一条边

于是问题变成：

是否存在一个大小为 n 的二分图匹配

也就是是否存在完美匹配。

实现上直接使用 DFS 版匈牙利算法：

枚举每一行，尝试给它找一个列
如果目标列已经被别的行占了，就递归尝试让那一行换到别的列
最终如果匹配数等于 n，答案就是 Yes

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;

int T;
int n;
int a[MAXN][MAXN];
vector<int> g[MAXN];
int match_col[MAXN];  // match_col[j] 表示第 j 列当前匹配了哪一行
int vis[MAXN];        // vis[j] 表示这一轮增广里，第 j 列是否已经尝试过

// 尝试给第 u 行找一个可用的列。
bool dfs(int u) {
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (vis[v]) {
            continue;
        }
        vis[v] = 1;

        // 如果这一列还没人占，或者原来占着它的那一行
        // 还能换到别的列，那么就把这一列分配给当前行。
        if (match_col[v] == 0 || dfs(match_col[v])) {
            match_col[v] = u;
            return true;
        }
    }
    return false;
}

void init_case() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            if (a[i][j] == 1) {
                g[i].push_back(j);
            }
        }
    }
}

bool solve_case() {
    memset(match_col, 0, sizeof(match_col));

    int match_cnt = 0;
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        if (dfs(i)) {
            match_cnt++;
        }
    }
    return match_cnt == n;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        init_case();
        if (solve_case()) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}

复杂度

设黑格总数为 E
时间复杂度： $O(nE)$ ，最坏为 $O(n^3)$
空间复杂度： $O(n^2)$

总结

这题最重要的不是匹配模板本身，而是先完成这一步转化：

从“交换行列”转成“挑选互不冲突的黑格”

一旦看出题目本质是在给“行”和“列”做一一配对，就可以自然地建成二分图最大匹配。

一图流解析

这张图把本题的建模、匹配过程、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[ZJOI2007] 矩阵游戏

目录

题意

思路

代码

复杂度

总结

一图流解析