题解 P3208 【[HNOI2010]矩阵】

· · 题解

调一年后终于过了，兴奋地点开了题解，然后居然是

dfs+剪枝

然后楼下大神的代码只有60行，emm

哎简单讲一下我的做法，2-sat+前缀和优化建图+bitset压位 首先发现确定第一行和第一列就可以确定整个矩阵，而且矩阵第i行第j列的值一定可以通过(1,1)(i,1)(1,j)三个值算出来。由于每个格子的取值范围很小，我们不妨枚举第一个格子的取值，那么整个矩阵的限制就会转化为l\leq(i,1)\pm(1,j)\leq r 其中l和r都是可以通过矩阵的信息算出来的。

然后对于将每个(1,j)和(i,1)的取值拆成P个状态，第i状态表示这个格子是否可以取小于等于i的值，根据2-sat对每个状态建true和false两个点，然后i的true向i+1的true连边，因为如果取了小于等于i那一定取i+1，同时第p-1个格子一定选，那么将p-1的false向p-1的true连边。

对于节点之间不等式的关系我们将大于和小于拆成两条限制，然后建边。不妨以

l\leq(i,1)+(1,j)$为例（$(i,1)+(1,j)\leq r$和这个是一样的）。我们枚举$(i,1)$的取值。假设我们令$(i,1)\leq k$，那么可得$(1,j)\gt l-k-1

所以我们将(i,1)的k号节点的true向(1,j)的l-k-1的false连边（false表示小于等于不成立也就是大于）即可。

最后跑2-sat，由于要求字典序最小所以需要用O(VE)的那个暴力算法，但是这样过不了所以可以用bitset压一下变成O(\frac{VE}{64})就可以过了