首页 > 其他 > 详细

【养生】NOIP模拟赛

时间:2017-09-05 20:26:14      阅读:213      评论:0      收藏:0      [点我收藏+]

第一场:9.4

T1:n个点的树,k个特殊点要求断k-1条边使它们分开,求最小代价。

算法:排序+并查集||树型DP

题解:从大到小排序边权后依次枚举,若两端点特殊则断边,若一端点特殊则合并传递,若无端点特殊则合并。

这是常见的【排序+并查集】的套路,这道题特殊在要从大到小排序后选择保留边,这样是为了并到最后两个点间路径只剩最小的一条,方便判断,正难则反

T2:哈希O(n)判断。

 

第二场:

 

 

第三场:

【养生】NOIP模拟赛

原文:http://www.cnblogs.com/onioncyc/p/7481750.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!