题解 CodeChef March Lunchtime 2015 No Unpaired Chefs
中文题面 题目链接 题意: 给你一个矩阵$M$,满足$M_{i,j}=M_{j,i}$，且$M_{i,j}>=0$。 让你构造一个矩阵$P$,满足： $P$是对称矩阵。 $P_{i,j}$要么等于零，要么等于$M_{i,j}$。 存在一个$S>0$,使得$P+P^2+…+P^S$中每个元素都是正数。 最小化$P$中元素和。 $M$是一个邻接矩阵，可以看成一个完全图。 我们知道$(M^k)_{i,j}$对应所有走$k$条边从$i$到$j$边权乘积的和。 满足第3个条件就需要所有点两两可达。 于是就是最小生成树了。 ...