题解：CF2043E Matrix Transformation

ax_by_c · 2024-12-27 11:42:47 · 题解

首先显然是拆位，原操作相当于把某行全部变成 0 或者把某列全部变成 1。

考虑把所有的 n+m 个操作看成点，如果一个操作执行后另一个操作必须执行则连有向边，可以根据 B 将图建出来。

接下来找到 A,B 中的元素变化情况，每一个变化都对应了一个操作，只需要判断从这些操作的对应点出发是否有环即可。（有环说明要一直执行，所以无解。）

时间复杂度 O(Tnm\log V)。

#include<bits/stdc++.h>
using namespace std;
namespace ax_by_c{
const int N=1e3+5;
int n,m,a[N][N],b[N][N];
vector<int>g[N*2];
bool mk[N*2];
void dfs(int u){
    if(mk[u])return ;
    mk[u]=1;
    for(auto v:g[u])dfs(v);
}
int in[N*2];
queue<int>q;
bool check(int x){
    x=1<<x;
    for(int i=1;i<=n+m;i++){
        g[i].clear();
        mk[i]=0;
        in[i]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(b[i][j]&x)g[i].push_back(n+j);
            else g[n+j].push_back(i);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if((a[i][j]&x)&&!(b[i][j]&x))dfs(i);
            if(!(a[i][j]&x)&&(b[i][j]&x))dfs(n+j);
        }
    }
    int cnt=0;
    for(int i=1;i<=n+m;i++){
        if(mk[i]){
            cnt++;
            for(auto v:g[i]){
                if(mk[v])in[v]++;
            }
        }
    }
    while(q.size())q.pop();
    for(int i=1;i<=n+m;i++){
        if(mk[i]&&!in[i])q.push(i);
    }
    while(q.size()){
        cnt--;
        int u=q.front();
        q.pop();
        for(auto v:g[u]){
            if(mk[v]){
                in[v]--;
                if(!in[v])q.push(v);
            }
        }
    }
    return !cnt;
}
void slv(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)scanf("%d",&b[i][j]);
    }
    for(int i=0;i<=29;i++){
        if(!check(i)){
            puts("No");
            return ;
        }
    }
    puts("Yes");
}
void main(){
    int T;
    scanf("%d",&T);
    while(T--){
        slv();
    }
}
}
int main(){
    ax_by_c::main();
    return 0;
}