10月杂题

？？怎么已经十月了？？？

1. Magic Matrix

首先意识到 \(a_{i,j}=a_{j,i}\) 是关键性质。

Solution 1：

令 \(d_{i,j}=\min\{\max\{a_{i,k},a_{k,j}\} \mid 1\le k\le n\}\)，考虑求所有的 \(d_{i,j}\)。

首先把 \(a\) 排序，考虑依次更新 \(d\)。

发现可以 bitset 做到 \(O(\frac{n^3}{\omega})\)。

Solution 2：

观察 \(a_{i,j}\le \max\{a_{i,k},a_{k,j}\}\)。

把 \(a_{i,j}\) 看成图上 \(i\rightarrow j\) 的权值。

则等价于：任意一个三元环不存在严格最大值。

可以证明：其等价于任意一个简单环上不存在严格最大值。

证明：假设存在严格最大值，将简单环进行三角剖分即与三元环不存在严格最大值的条件矛盾。

然后最小生成树即可。

时间复杂度 \(O(n^2 \log n^2)\)。

记录