LQ公司是世界著名的石油公司，为世界供应优质石油，最近，LQ公司又在森林里发现了一大片区域的油田，可以在这个油田中开采n个油井，LQ公司在这n个油井之间修建了n-1条道路，每条道路连接两个油井，路径中间不会路过任何油井，而且这些道路将所有油井连通，在保证总路径长度最短的情况下，LQ公司至少需要花费多少人力才能完成所有油井的建立与维护。
LQ公司是世界著名的石油公司，为世界供应优质石油。 最近，LQ公司又在森林里发现了一大片区域的油田，可以在这个油田中开采n个油井。 LQ公司在这n个油井之间修建了n-1条道路，每条道路连接两个油井，路径中间不会路过任何油井，而且这些道路将所有油井连通。 建立油井的时候需要使用一台大型设备，运输起来非常麻烦，LQ公司准备在其中的一个油井位置建立一个空运站，先将设备空运到空运站，之后每次经过他们建立的道路来运输这个大型设备以建立不同的油井，当油井建立完毕后再从空运站将大型设备运走。 为了减少运输的麻烦，公司要求大型设备在道路上运输的总路程是最短的。 在建立油井和采油的过程中需要花费一些人力，第i个油井需要花费Bi个人，而一旦油井建成，就需要Si个人一直坚守在油井上进行维护。 当然，如果一个人参与了油井的建设，他可以直接留下来维护油井，或者参与下一个油井的建设，但是在维护油井的人不能再参加后续油井的建设了。 现在LQ公司想知道，大型设备运输的总路径长度最短是多少？在保证总路径长度最短的情况下，LQ公司至少需要花费多少人力才能完成所有油井的建立与维护。
（图片来源网络，侵删）
标签： 蓝桥杯2290: 蓝桥杯2018年第九届真题-采油题解
文章来源：
arkfactor
版权声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。
