题解：P1418 [TJOI2011] 构造矩阵

· · 题解

先用最大流求出任意一个合格矩阵,再用如下 BFS 修改矩阵.
我们注意到如果想把一个位置的1修改成0,这个点的行和列都需要一个0修改成1,反之亦然,如此反复,如果形成了一个回路则可以修改最初的那个位置
形式化来讲就是:

a_{i,j}=1$ $\to$ $a_{i,k}=0$ $\to$ $a_{s,k}=1 \to$ $\dots$ $\to$ $a_{i,j}=1

如果能找到这样一条回路,那么就可以把路径上的点异或 1 后依然是一个合格矩阵.
我们以行和列为状态,行转移这一行上点等于0的列,列转移这一列上点等于1的行,这样转移路径上行列是交错的,然后递归修改交点即可.
修改一次复杂度为 O((n+m)^2)
要枚举每个点然后修改所以总复杂度为 O(nm(n+m)^2) 基本上达不到理论复杂度,可以通过此题
提交记录 

#include <bits/stdc++.h>
using namespace std;
struct root {
  int t;
  int x;
} qq[1000001], accq[101][101];
int g[211][211], n, m, r, q[1000001], ac[1000001], ans[111][111], acc[101][101],acq[1000001];
void bfs(int x, int y) {
  int l = 0, r = 0;
  for (int i = 1; i <= max(n, m); i++) {
    accq[1][i] = accq[2][i] = {0, 0};
    acc[1][i] = acc[2][i] = 0;
  }
  qq[r++] = {1, x};
  acc[1][x] = 1;
  while (r > l) {
    root now = qq[l++];
    if (now.t == 2 && now.x == y) {
      ans[x][y] ^= 1;
      //递归输出交点
      while (1) {
        root qs = accq[now.t][now.x];
        if (!qs.x) break;
        if (now.t == 2)
          ans[qs.x][now.x] ^= 1;
        else
          ans[now.x][qs.x] ^= 1;
        now = qs;
      }
      break;
    }
    if (now.t == 1) {
      //不能跑已经处理过的点
      for (int i = now.x == x ? y : 1; i <= m; i++)
        if (ans[now.x][i] == 0 && !acc[2][i]) {
          qq[r++] = {2, i};
          acc[2][i] = 1;
          accq[2][i] = {now.t, now.x};
        }
    } else {
      //不能跑已经处理过的点
      for (int i = x; i <= n; i++)
        if (ans[i][now.x] == 1 && !acc[1][i]) {
          qq[r++] = {1, i};
          acc[1][i] = 1;
          accq[1][i] = {now.t, now.x};
        }
    }
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> r;
    g[0][i] = r;
  }
  for (int j = 1; j <= m; j++) {
    cin >> r;
    g[j + n][n + m + 1] = r;
  }

  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) g[i][j + n] = 1;
  //最大流
  while (1) {
    int l = 0, r = 0;
    q[r++] = 0;
    ac[0] = 1;
    for (int i = 1; i <= n + m + 1; i++) ac[i] = acq[i] = 0;

    int f = 1;
    while (r > l) {
      int now = q[l++];
      if (now == n + m + 1) {
        while (now) {
          g[acq[now]][now]--;
          g[now][acq[now]]++;
          now = acq[now];
        }
        f = 0;
        break;
      }
      for (int i = 0; i <= n + m + 1; i++)
        if (!ac[i] && g[now][i]) {
          q[r++] = i;
          acq[i] = now;
          ac[i] = 1;
        }
    }
    if (f) break;
  }
  //找到一个合理矩阵
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (g[j + n][i]) ans[i][j] = 1;

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      //如果是1看看能不能变成0
      if (ans[i][j] == 1) {
        bfs(i, j);
      }
    }
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cout << ans[i][j];
    }
    cout << '\n';
  }
}