题解：P11942 [KTSC 2025] 重塑矩阵 / grid_encoding

· · 题解

NB 题。

我们建立一张 2n 个点的有向图代表这个矩阵的行和列，某个位置是 1 就行向列连边，是 0 就列向行连边。不难发现这是一张二分图。

那么我们回过头看题目里那个条件实际上在说，这两行两列构成了一个四元环。那么约束实际上就是，这张二分图里不存在四元环。现在考虑如果这张二分图存在六元环 abcdef，考查 b 和 e 之间的连边状况，不难发现一定存在四元环，矛盾。于是这张二分图不存在六元环，以此类推，不存在偶环。同时二分图里没有奇环，于是这是一张 DAG。

二分图将所有点分为两色，一黑一白，在原题中就对应行节点和列节点。我们考查所有无入度的点，于是它们之间一定两两无边，于是它们全都同色，并且任意删掉一些点，剩余的无入度点也都会满足这一点。于是把这些点全部删掉后新的无入度点也一定都同色，且一定和第一批点异色，且在这两批点里任意各选一个都一定有第一批连向第二批的边。以此类推，最终这个图是被分成了若干层。任取两个异色点，层高的连向层低的。注意这里“层”的定义和批是反的。

于是现在只需要确定每个节点的层就可以了。我们只需要传过去一个森林，保证原图中每个点都有层恰好比它高 1 的点连向它（只要有），根恰好是最低层的所有点，就做完了。

#include <bits/stdc++.h>
using namespace std;
void select(int x, int y);
void send(vector<vector<int>> A) {
  int n = A.size();
  vector<int> cx(n), cy(n);
  function<void(int)> dfsx, dfsy;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) ++(!A[i][j] ? cx[i] : cy[j]);
  dfsx = [&](int i) {
    cx[i] = -1;
    for (int j = 0; j < n; ++j)
      if (A[i][j] == 1) --cy[j];
    for (int j = 0; j < n; ++j)
      if (A[i][j] == 1 && !cy[j]) select(i, j), dfsy(j);
  };
  dfsy = [&](int j) {
    cy[j] = -1;
    for (int i = 0; i < n; ++i)
      if (A[i][j] == 0) --cx[i];
    for (int i = 0; i < n; ++i)
      if (A[i][j] == 0 && !cx[i]) select(i, j), dfsx(i);
  };
  for (int i = 0; i < n; ++i)
    if (!cx[i]) dfsx(i);
  for (int j = 0; j < n; ++j)
    if (!cy[j]) dfsy(j);
}
vector<vector<int>> reconstruct(vector<vector<int>> B) {
  int n = B.size();
  vector<int> dx(n), dy(n);
  function<void(int)> dfsx, dfsy;
  dfsx = [&](int i) {
    for (int j = 0; j < n; ++j)
      if (B[i][j] == 1 && !dy[j]) dy[j] = dx[i] + 1, dfsy(j);
  };
  dfsy = [&](int j) {
    for (int i = 0; i < n; ++i)
      if (B[i][j] == 0 && !dx[i]) dx[i] = dy[j] + 1, dfsx(i);
  };
  for (int i = 0; i < n; ++i) {
    int j = 0;
    while (j < n && B[i][j] != 0) ++j;
    if (j == n) dfsx(i);
  }
  for (int j = 0; j < n; ++j) {
    int i = 0;
    while (i < n && B[i][j] != 1) ++i;
    if (i == n) dfsy(j);
  }
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) B[i][j] = dx[i] < dy[j];
  return B;
}