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