题解：P11543 [Code+#5] 二分图判定

_miss_ · 2025-01-10 16:08:17 · 题解

刚看到本题，二分图？？我不会啊。但仔细读了一遍题，这不是水题吗。

题意

给定两个 01 矩阵 A 和 B，判断是否可以通过以下两种操作将 A 转换为 B：

• 行翻转：选择 A 的一行，将 0 变为 1，1 变为 0。
• 列翻转：选择 A 的一列，将 0 变为 1，1 变为 0。

思路

由于异或运算的特性：

• 相同的值异或结果为 0。
• 不同的值异或结果为 1。

考虑将矩阵 B 的元素与矩阵 A 的对应元素进行异或运算 A[i][j] ^= B[i][j]，操作后问题转化为判断是否可以通过行列翻转将矩阵 A 的所有元素变为 0。

如果 A[i][j] 异或后为 0，则表示原 A 和 B 对应位置相同，否则表示不同。

进一步简化，假设第一行不进行翻转操作，那么，其他行和列的翻转操作就确定了。

如果第一行需要翻转，那么其他行和列的翻转操作也会相应改变。

因此，我们只需要考虑第一行是否翻转两种情况，而不需要枚举所有行的翻转情况。

注意到以下性质：

• 如果可以通过行列翻转将 A 转换为 B，那么对于矩阵 A 中任意一行，它要么与第一行完全相同，要么与第一行完全相反。
• 换句话说，每一行要么和第一行所有元素都相同，要么所有元素都相反（0 变 1，1 变 0）。

经过上述分析，我们不需要真正去模拟，就能得到最终的判定结果。

Code

#include <iostream>
using namespace std;
int a[1005][1005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m; // n: 行数, m: 列数
    cin >> n >> m;
    // a: 存储矩阵 A
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) 
            cin >> a[i][j];
    }
    // 读取矩阵 B，并与矩阵 A 进行异或操作
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int b; // b: 临时变量，存储矩阵 B 的元素
            cin >> b;
            a[i][j] ^= b;
        }
    }
    // 检查每一行是否与第一行满足条件
    for (int i = 1; i < n; ++i) {
        int k = 0; // k: 记录当前行与第一行相同元素的个数
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == a[0][j]) 
                k++;
        }
        // 如果当前行既不与第一行完全相同，也不与第一行完全相反，则输出 "Budexing"
        if (k != 0 && k != m) {
            cout << "Budexing";
            return 0;
        }
    }
    // 如果所有行都满足条件，则输出 "Koyi"
    cout << "Koyi";
    return 0;
}