Description：

称一个矩阵为魔法矩阵，当且仅当满足一下三点： $a_{i,j}=a_{j,i},a_{i,i}=0,a_{i,j}\leqslant \max(a_{i,k},a_{k,j})$ 。 单次询问一个矩阵是否为魔法矩阵。

$n\leqslant2500$

Solution1：

首先当然是把原矩阵看成距离矩阵。 $$ \begin{align} a_{i,j}\leqslant\max(a_{i,k},a_{k,j})\Rightarrow a_{i,k}\leqslant\max(a_{i,j},a_{j,k}),a_{k,j}\leqslant\max(a_{k,i},a_{i,j}) \end{align} $$ 只是交换下标而已，但是注意到，上面那个式子说明任意一个三元组最大边权的边一定至少有两个，那么我们就可以把所有边按长度排序，依次加入，然后要求任意时刻不能有一个三元组只有两条边，这也就是说任意时刻都必须是一个完全图，于是用并查集统计联通块内点数和边数检查就行了。

Solution2：

首先先用 $kruskal$ 求出来一个最小瓶颈生成树，设 $f_{i,j}$ 表示树上 $i$ 和 $j$ 路径上的最大边权，那么显然有 $a_{i,j}\geqslant f_{i,j}$ ，不然肯定 $f_{i,j}$ 不优，然后 $a_{i,j}\leqslant\max(a_{i,k},a_{k,j}),a_{i,k}\leqslant\max(a_{i,l},a_{l,k})\Rightarrow a_{i,j}\leqslant \max(a_{i,k_1},a_{k_1,k_2}\dots,a_{k_m,j})$ ，于是有 $a_{i,j}\leqslant f_{i,j}$ ，因此 $a_{i,j}=f_{i,j}$ ，然后就可以检查了。