题解：P16443 [XJTUPC 2026] 矩阵拆分

Nuclear_Fish_cyq · 2026-05-10 18:56:51 · 题解

首先显然 B_{i,j}=B_{j,i}。且 B_{i,i} 是偶数。

接下来对于其他的 B_{i,j} 我们分类讨论：

• 如果 B_{i,j} 是偶数那么 A_{i,j}=A_{j,i}=\frac{B_{i,j}}{2}。
• 如果 B_{i,j} 是奇数那么我们需要给多余的一个 1 分配到 A_{i,j} 与 A_{j,i} 中的一个上。这时候我们考虑其他限制，那么这个问题变成了：

有一些点，你需要黑白染色，且保证每一列黑白点数量差不超过 1。

然后这题是 CF547D，具体做法是：

我们考虑把点建模成边，然后用度数来建模性质。更具体地，给每一行每一列都建一个点，如果有点 (x,y) 就连接对应的行和列。如果我们提前用一个点来消去所有奇点的话，那么这东西就是一个欧拉回路。

建模部分：

for(int i = 1; i <= n; i++){
  for(int j = 1; j < i; j++){
    if(b[i][j] % 2){
      add(i, j + n);
      deg[i]++;
      deg[j + n]++;
    }
  }
}
for(int i = 1; i <= 2 * n; i++){
  if(deg[i] % 2){
    add(0, i);
  }
}
redirect();