思路与算法

先求覆盖全部左点的匹配，若不足N则所有位置输出1。把非匹配边定向为左→右，匹配边定向为右→左，求SCC；同时在反图从未匹配右点出发标记能通往空闲右点的顶点。原匹配边可用，非匹配边当两端同SCC或其右端能通往空闲右点时可用，其余和原本不存在的边输出1。

正确性说明

两个满左匹配的对称差由交替环和连接不同空闲右点的交替路径组成。一个非匹配边可出现在新匹配中，当且仅当它能参加交替环，或从该右端继续到空闲右点的交替路径。前者等价两端同SCC，后者等价上述可达性；翻转对应环/路径就构造出见证匹配。

复杂度

输入和输出O(NM)，Kuhn最坏O(N²M)，交替图构建、两遍DFS与反向搜索O(NM+N+M)。空间O(NM+N+M)，所有数组和矩阵初始化均计入。

易错点

输出0表示这条边可出现在某个满左匹配，1表示不可以，方向与常规邻接表相反。M可大于N，空闲右点是必要条件，不能只看SCC。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (auto &s : a)
        cin >> s;
    vector<int> mt(m, -1), left(n, -1), seen(m);
    function<bool(int)> aug = [&](int u) {
        for (int v = 0; v < m; v++)
            if (a[u][v] == '1' && !seen[v]) {
                seen[v] = 1;
                if (mt[v] < 0 || aug(mt[v])) {
                    mt[v] = u;
                    left[u] = v;
                    return true;
                }
            }
        return false;
    };
    for (int i = 0; i < n; i++) {
        fill(seen.begin(), seen.end(), 0);
        if (!aug(i)) {
            for (int k = 0; k < n; k++)
                cout << string(m, '1') << '\n';
            return 0;
        }
    }
    int N = n + m;
    vector<vector<int>> g(N), h(N);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (a[i][j] == '1') {
                int u = i, v = n + j;
                if (left[i] == j)
                    swap(u, v);
                g[u].push_back(v);
                h[v].push_back(u);
            }
    vector<int> vis(N), order, comp(N, -1);
    function<void(int)> dfs = [&](int u) {
        vis[u] = 1;
        for (int v : g[u])
            if (!vis[v])
                dfs(v);
        order.push_back(u);
    };
    for (int i = 0; i < N; i++)
        if (!vis[i])
            dfs(i);
    function<void(int, int)> paint = [&](int u, int c) {
        comp[u] = c;
        for (int v : h[u])
            if (comp[v] < 0)
                paint(v, c);
    };
    reverse(order.begin(), order.end());
    int cc = 0;
    for (int u : order)
        if (comp[u] < 0)
            paint(u, cc++);
    queue<int> q;
    vector<int> can(N);
    for (int j = 0; j < m; j++)
        if (mt[j] < 0) {
            can[n + j] = 1;
            q.push(n + j);
        }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : h[u])
            if (!can[v]) {
                can[v] = 1;
                q.push(v);
            }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << (a[i][j] == '1' && (left[i] == j || comp[i] == comp[n + j] || can[n + j])
                         ? '0'
                         : '1');
        cout << '\n';
    }
}