HashTag:

POJ 3156 Interconnect

MayFlyyh | Hash, 期望 | 2018-08-11
> 现在有n个点,给你m条边,每次随机选2个点连边(可能选已经连过的)并且花费1个代价,求使n点联通的期望最小代价。 --- 本题关心每个联通块的规模,但不关心每个联通块具体的点。 然后根据规模记忆化搜索,因为规模无法正常表示成值,所以每次hash一下当前dp的状态,然后记忆化搜索看是否已经算过并返回答案。 对于每个联通块,有两种情况,... [阅读全文]
Ɣ回顶部