我只对问题陈述有疑问,我不想实施。如果你能给我一个想法,我会试着接近自己。
我正在解决Doomsday问题,我没有得到这一行:
政府在每个城市建造了
pi
吊舱,以便在发生任何灾难时将人们带到地球并进行自毁。
我知道人们坐在豆荚里,但坐在豆荚后他们会去哪里?假设每个城市有5个城市(1,2,3,4,5)有一些人口,那么目标城市(顶点)应该作为拯救生命的目的地?
问题描述:
今天对于Krypton的每个人来说都只是一个常规日,直到有消息说流星将在X分钟内摧毁Krypton。
Krypton有N个城市通过双向道路连接在一起.RAD DESCRIPTION:从
t
th城市到i
城市j
需要1<=i,j<=N
分钟,i j t
格式为qi
。政府在每个城市建造吊舱,以便在遇到任何灾难时将人们运送到地球并进行自毁。每个城市都有Doomsday人口。一旦人们听到这个消息,他们就会试图通过在流星摧毁一切之前在他们自己的城市或其他城市获取这些吊舱来拯救自己。请注意,一个吊舱只能携带一个人。给出最少数量的人死亡。举例说明澄清。
问题链接:qazxswpoi
我知道人们坐在豆荚里但坐在豆荚后他们去哪里,假设有5个城市(1,2,3,4,5)每个城市有一些人口,应该是什么目标城市(顶点) )作为拯救生命的目的地。
一旦有人登上了吊舱,我们就会认为这个人已经救了。 因此,这个问题的目的是最大化在小行星撞击地球之前将在舱内的人数。最终意味着,您必须找到一种“聪明”的方式来在城市之间移动适当数量的人,以便优化容器,因为您可以移动人而不是移动容器。