![P11942 [KTSC 2025] 重塑矩阵 题解](images/page-header-bg.jpg)
![P11942 [KTSC 2025] 重塑矩阵 题解](http://pic.xiahunao.cn/yaotu/P11942 [KTSC 2025] 重塑矩阵 题解)
Solution看到 0101 矩阵一个经典的转化是转化成二分图建立 nn 个行点 R0∼Rn−1R0∼Rn−1 与 nn 个列点 C0∼Cn−1C0∼Cn−1Ai,jAi,j 表示一条连接 Ri,CjRi,Cj 的边。在此基础上可以想到两种建图方法Method 1建无向图Ai,jAi,j 作为边权。不难发现原限制是 0/10/1 边各自的边导出子图为连通图的充分不必要条件。2n−12n−1 条边恰好是一个生成树但是发现生成树不好构造我们就卡住了。Method 2建有向图Ai,jAi,j 表示方向转化成二分竞赛图若 Ai,j1Ai,j1建边 Ri→CjRi→Cj若 Ai,j0Ai,j0建边 Cj→RiCj→Ri那么原条件等价于原图中没有四元环。进一步地可以归纳证明这样的二分图一定无环。即二分竞赛图中无四元环等价于整张图无环。现在问题转化成了如何用 2n−12n−1 条边表示这样一个有向无环二分图。我们只需要知道任意两点间的拓扑序大小关系。注意到若当前图中存在 kk 个入度为 00 的点在不取完这 kk 个点之前是不可能产生新的入度为 00 的点的。这样一层层剥掉入度为 00 的点就将图分成了若干层。显然同层内一定无边。那么我们只需要知道每个点所在的层。显然除第一层外每个点必须有来自前一层的入边。对于每个点我们随便记录一条这样的边会得到一个外向有向树森林其中根为第一层的点点在树中的深度就是它所在的层号。然后就做完了。Code#include grid_encoding.h#include vector#include cstring#define rep(i,a,b) for(int i(a);ib;i)#define rept(i,a,b) for(int i(a);ib;i)#define eb emplace_backusing namespace std;namespace{const int N1005;int n,in[N],d[N];vectorint g[N],q;}void init(){memset(in,0,sizeof(in));memset(d,0,sizeof(d));rep(i,0,n*2) g[i].clear();q.clear(),q.reserve(n1);}void send(vectorvectorint A){nA.size(),init();rep(i,0,n) rep(j,0,n){if(A[i][j]) g[i].eb(jn),in[jn];else g[jn].eb(i),in[i];}rep(i,0,n*2) if(!in[i]) q.eb(i);while(!q.empty()){int uq.back();q.pop_back();for(int v:g[u]){if(!--in[v]){q.eb(v);vn?select(u,v-n):select(v,u-n);}}}}vectorvectorint reconstruct(vectorvectorint B){nB.size(),init();rep(i,0,n) rep(j,0,n){if(B[i][j]1) g[i].eb(jn),in[jn];else if(B[i][j]0) g[jn].eb(i),in[i];}rep(i,0,n*2) if(!in[i]) q.eb(i);while(!q.empty()){int uq.back();q.pop_back();for(int v:g[u]){if(!--in[v]){d[v]d[u]1;q.eb(v);}}}rep(i,0,n) rep(j,0,n){if(B[i][j]-1) B[i][j]d[i]d[jn];}return B;}
