2260: 商店购物 && 4349: 最小树形图 朱刘算法

2260的数据应该有误,存在自环,然而网上的题解一看都是一个样子。。。

简直了。。。重点是还能跑出来?!

这题就是最小树形图的板子题。

我的代码必须强行跑一次朱刘才能过2260

 

思路大致如下:
考虑到不存在自环时,每个点一定除了第一次以外均会被以最优方式更新,因为每个物品最少购买一次,

所以有最优依赖关系的可以在买依赖点后一次性买完。

然后对于每个物品求出其最优依赖点,然后发现构成的图要么是树,要么存在环。

若是存在环,只需要把这个环内的所有权加入最终答案,然后考虑这个环的起点,

减去起点的当前最优点即可。

然后循环这个操作直到不存在环。

c++代码如下:

 

5 + 8 =