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

· · 题解

先判断何时无解：当存在 b_{i,i}\equiv1\pmod2 或 b_{i,j}\not=b_{j,i} 时。

然后我们发现将 \lfloor b_{i,j}\rfloor 各分配给 a_{i,j} 和 a_{j,i} 不会导致剩下的部分无解，于是问题就在于剩下的 b_{i,i}\equiv1\pmod2 的 1 分配给哪边。

然后就可以建图了：若 b_{i,j}\equiv1\pmod2，连边 i\leftrightarrow j（因为 b 是对称的，所行和列对应的点可以合并为一个）

然后我们需要对边 01 染色，使得一个点所连接的 0 边和 1 边数量相差不超过 1。

然后可以发现对于一个环，将入边设为 0，出边设为 1，这样一个点连接 0 和 1 的数量是相等的。

似乎也不需要欧拉回路，直接 dfs 每次消去一个环即可。最终会剩下若干条链，这样两端 0 和 1 的数量会相差 1，不过也没事。

#include <bits/stdc++.h>
#define ll long long
#define F(i,l,r) for(ll i=l;i<=r;i++)
using namespace std;
ll rd(){ll x=0;char c=getchar();while(!isdigit(c))c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar();return x;}
ll n,a[2205][2205],e[2205][2205],pp[2205],in[2205],b[2205][2205];
void dfs(ll u){
    for(ll i=pp[u];i<=n;i=pp[u]){
        pp[u]=i+1;
        if(e[u][i]==1){
            e[u][i]=4,e[i][u]=3;
            in[u]--,in[i]--;
            dfs(i);
            return;//////每次只消去一个环 
        }
    }
}
void sov(){
    n=rd();F(i,1,n)F(j,1,n)a[i][j]=rd();
    F(i,1,n)F(j,1,n)if(a[i][j]!=a[j][i]||i==j&&a[i][j]%2){printf("No\n");return;}
    printf("Yes\n");
    F(i,1,n+1)F(j,1,n+1)e[i][j]=0;
    F(i,1,n+1)in[i]=0,pp[i]=1;
    F(i,1,n)F(j,1,n)if(a[i][j]&1)e[i][j]=1,in[i]++;
    F(i,1,n)if(in[i]%2)dfs(i);
    F(i,1,n)while(in[i])dfs(i);
    F(i,1,n){
        F(j,1,n)b[i][j]=a[i][j]/2+(e[i][j]==4);
        F(j,1,n)printf("%lld ",a[i][j]/2+(e[i][j]==4));
        printf("\n");
    }
}
int main(){ll t=rd();F(i,1,t)sov();return 0;}
/*
1 8
0 0 0 0 0 0 1 1
0 0 0 1 0 1 1 0
0 0 0 0 0 1 1 0
0 1 0 0 0 0 1 1
0 0 0 0 0 0 0 1
0 1 1 0 0 0 0 1
1 1 1 1 0 0 0 0
1 0 0 1 1 1 0 0
*/