CF632F Magic Matrix

description

这个有点太形式化了，还是不放了。

solution

首先让我们注意到 \(a_{i, j} \le \max ( a_{i, k}, a_{j, k} )\) 等价于 \(a_{i, j} \le \max ( a_{i, k}, a_{k, j})\)，然后转化为这个形式后就会发现可以将其理解成一张图，不存在一条从 \(i \to j\) 的路径满足这条边上所有值都小于 \(a_{i, j}\)。

然后这个过程我们也是非常熟悉的，因为最小瓶颈树等价于最小生成树，于是我们搞出其最小生成树，然后我们用个啥子倍增或者树链剖分维护一下树上链 \(\max\)，或者你也可以在求解最小生成树的过程中，如果已经存在一条从 \(i \to j\) 的路径，那么就是不行的（要把相等的一起处理）。

然后无论咋做都行了。