题解 CodeChef March Lunchtime 2015 No Unpaired Chefs

中文题面
题目链接
题意:
给你一个矩阵$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需要特判。
考试时因为这个坑惨。

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框