【寒假作业】【NOIP2013】货车运输

恩 这道题我居然一遍AC 没有写萎233【理论上来说这种树/图问题我都得调1h+

首先这个最优的路肯定是在最大生成树上的。。严谨的来说是最大生成森林

为什么呢?

如果你选了最大生成树上的一条链,但将一条边替换成另外的边/链会更优。。那么最大生成树就不应该包含这条边而是另外的了。。

所以先找出最大生成森林,然后在上面倍增就可以了。。

说点什么

您将是第一位评论人!

提醒
wpDiscuz