3058. 四叶草魔杖
时间: 2023-10-31 20:53:48 浏览: 46
四叶草魔杖是一种神奇的武器,它由四件武器融合而成。当魔杖顶端生长出一棵四叶草时,它会散发出七色光芒。圆盘上镶嵌着N颗宝石,每颗宝石都有不同的能量。如果宝石的能量过高,需要将能量传递给其他宝石;如果能量过低,需要从其他宝石处获取能量。保证所有宝石的能量之和为0。只有当所有宝石的能量都相同时,才能插入四叶草魔杖并开启超自然之界的通道。然而,只有M对宝石之间可以互相传递能量,每对宝石之间传递能量都需要花费一定的代价。
探险队员们想知道,为了使所有宝石的能量都相同,最少需要花费多少代价。给定宝石的数量N,每对宝石之间传递能量的代价Ti,以及每颗宝石的能量Ai,你需要输出一个整数表示答案。如果无法使所有宝石的能量相同,则输出"Impossible"。
范例输入:
3
3
50 -20 -30
0 1 10
1 2 20
0 2 100
范例输出:
30
提示: 本题可以使用动态规划来解决,具体的解题思路可以参考动态规划的相关知识。
#### 引用[.reference_title]
- *1* [【NOIP2013模拟】四叶草魔杖 题解](https://blog.csdn.net/CMC_YXY/article/details/118528208)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control,239^v3^insert_chatgpt"}} ] [.reference_item]
- *2* *3* [BZOJ_3058_四叶草魔杖_kruscal+状压DP](https://blog.csdn.net/diaopang1934/article/details/102276134)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]