题解：P16840 [GKS 2021 #A] Checksum

· · 题解

题意简化

有一个 N\times N 的 0/1 矩阵，有些格子是 -1，表示不知道它的值。

已知每一行、每一列的异或和。

你可以花费 B_{i,j} 的费用直接恢复某个未知格 A_{ij}。

恢复一些格子后，剩下的未知格可以利用行、列的校验和（异或和）R_i,C_i 推导出来。

补全整个矩阵，使得每一行的异或和等于 R_i，每一列的异或和等于 C_i，求需要的最小总花费。

解题思路

首先我们需要理解什么情况下能使用校验和恢复。

因此，我们希望尽可能通过校验和免费推出未知格，而不是支付费用直接恢复。

也就是如果某一行或某一列当前只剩下一个未知格，就可以直接用该行或该列的异或和求出这个格子的值，不需要花费。

求出后，这个格子就变成已知，可能会让其他行或列也只剩下一个未知格，于是可以继续免费推出。 如果最后所有未知格都能这样被推出，那么总花费就是 0。

我们将行、列的编号看作节点，然后对于每一个数值为 -1 的位置 (x,y)（可以看作在坐标系中的 x,y 坐标），我们连接 x 和 y，边权为 b_{x,y}，此时我们得到了一张图。

注意：为了避免行、列编号冲突，通常将列节点编号设为 n+y，即行节点为 1\sim n，列节点为 n+1\sim 2n。

一个例子：

从这张图中我们可以得出，以下位置上的数值为 -1：

(1,1)
(1,5)
(4,3)
(4,5)
(6,7)
(8,7)

可以发现，位置 (6,7) 和 (8,7) 上的 -1 可以通过对应行的校验和直接求出，花费为 0，同理，还有位置 (1,1) 和 (4,3) 上的 -1 可以直接通过对应行和对应列的校验和求出。

将这些位置上的 -1 还原之后，剩下的 -1 也就可以全部通过校验和直接求出了，此时总花费为 0。

导致总花费为 0 的原因是什么？观察这些位置在图上的关系，可以发现，在某一时刻可以被直接求出的 -1 的位置所对应的边所连接的 x 和 y 节点其中必有一个节点的度数为 1（注意本文连接的边均为无向边），通俗一点说就是必有一个节点为叶子节点。

当我们将这些位置上的 -1 还原后，也就对应着图上的一条边被删除，删除这些边后，这条边所连接的两个节点的度数就会减一。

删除完本轮可以删掉的所有边之后，就会出现新的叶子节点。

如果可以按照以上步骤将所有的边全部删除，那么总花费将会为 0。

如果某一时刻没有可以免费推导的边了，说明图中出现了环（因为环上的节点的度数至少为 2（对于无向图）），此时我们就需要将其中的一些连接的边（对应着位置 (x,y)）花费 b_{x,y} 恢复该格子，直到出现可以直接删除的边为止。

重复以上过程，直到整张图所有的边被删完，总花费就是所有被直接恢复的格子的 b_{x,y} 之和。

明显我们想要让这个总和越小越好，但是我们又不知道删除哪些边可以既剩下的边可以全部直接删除又花费最少，这样做难度很大。

所以我们正难则反，既然“删除的边的花费最小”我们求不出来，我们就用所有边的总花费减去“保留的边花费最大”，这样就好求多了！

那么这个“保留的边花费最大”如何求？因为我们需要保证这个保留下来的边组成的是一个树形（森林）结构，又要保证这些边的边权总和最大，可以想到使用最大生成树（森林）解决。

时间复杂度 O(T\times n^2\log n)，对于 n=500,T=100 可以通过。

:::info[AC 代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e2+5;

int t;
int n;
int a[N][N];
int b[N][N];
int r[N],c[N];

struct node{
    int x,y,w;
};

vector<node> e;

bool cmp(node a,node b){
    return a.w>b.w; // 按边权从大到小排序。
}

int fa[2*N]; // 注意开 2*n 的空间。

// 并查集：

int get(int x){
    if(fa[x]==x)return x;
    return fa[x]=get(fa[x]);
}

void unite(int x,int y){
    x=get(x),y=get(y);
    if(x!=y)fa[x]=y;
}

int Case;

void solve(){
    Case++;
    e.clear(); // 注意多测。
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        } 
    }
    int sum=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>b[i][j];
            sum+=b[i][j]; // 总边权和。
            if(a[i][j]==-1){ // 如果该位置为 -1，连边。
                e.push_back({i,j+n,b[i][j]});   // 因为使用 (i,j) 作为边的左右端点会互相冲突，所以将其中一个节点的编号偏移 n，解决冲突的问题。
            }
        } 
    }
    for(int i=1;i<=n;i++)cin>>r[i]; // R 和 C 在本题中不影响答案，因为只要图是森林就一定能推出，保证有解。
    for(int i=1;i<=n;i++)cin>>c[i]; 
    int ans=0;
    for(int i=1;i<=2*n;i++)fa[i]=i; // 注意跑到 2*n。
    sort(e.begin(),e.end(),cmp); // 按边权从大到小排序。
    for(auto v:e){ // 最大生成树。
        int x=v.x,y=v.y,w=v.w;
        if(get(x)!=get(y)){
            unite(x,y);
            ans+=w;
        }
    }
    cout<<"Case #"<<Case<<": "<<sum-ans<<'\n'; // 输出。
}

signed main(){
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0)->sync_with_stdio(false);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

:::