中文题面
题目链接
题意:
给你一个矩阵$M$,满足$M_{i,j}=M_{j,i}$，且$M_{i,j}>=0$。
让你构造一个矩阵$P$,满足：

  1. $P$是对称矩阵。
  2. $P_{i,j}$要么等于零，要么等于$M_{i,j}$。
  3. 存在一个$S>0$,使得$P+P^2+…+P^S$中每个元素都是正数。
  4. 最小化$P$中元素和。

$M$是一个邻接矩阵，可以看成一个完全图。 我们知道$(M^k)_{i,j}$对应所有走$k$条边从$i$到$j$边权乘积的和。
满足第3个条件就需要所有点两两可达。
于是就是最小生成树了。

n=1需要特判。 考试时因为这个坑惨。