【BZOJ2654】tree

今天LCF的考试题

听说是臭垃圾陈立杰的题

这题的思路很巧妙:二分一个数,让所有白边的权值减去这个数然后求最小生成树,如果得到的最小生成树所含白边少于\(need\)那么说明二分的数需要减小使白边能够更多地进入最小生成树,代价是之后加回来的权值更大。否则可以将二分的数减小或者不变。

这题还有一个小细节:如果减去某个数后有相同权值的白边和黑边,优先加白边。想想就明白了。

1
说点什么

1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
游客
陈立杰

乡巴佬