一项工程由甲、乙、丙三个工程队共同完成需要15天,甲队与乙队的工作效率相同,丙队3天的工作量与乙队4天的工作量相当。三队同时开工2天后,丙队被调往另一工地,甲乙两队留下继续工作。那么,开工22天后,这项工程:
假如现在国家要进行一项工程,需要将图中9个城市用某种特殊缆线连接(只要任意两个城市之间都有至少一条通路即可,例如“北京”和“贵阳”,可以通过“北京”——“郑州”——“株洲”——“贵阳”连接起来)。
图中显示的是所有允许用缆线连接的城市以及连接的成本如图所示。
现在我们来讨论解决类似问题的方法。
①首先连接整幅图中成本最小的连接线,也就是“郑州”——“徐州”。之后把“郑州”和“徐州”看为一个整体,寻找其他城市中与他们之一相连成本最小的城市,也就是“徐州”——“上海”。然后将三个连接过的城市看为一个整体,找出其他城市与这三个城市之一连接成本最小的城市,也就是“北京”——“郑州”。就像这样,直到所有城市都连为一体。
②从每个城市出发,都有若干个允许连接的城市。首先对所有城市,连接它们与从它们出发允许连接的城市中连接成本最小的。例如从“郑州”出发,要连接“郑州”——“徐州”;从“贵阳”出发,要连接“贵阳”——“柳州”;从“柳州”出发,也要连接“贵阳”,但是已经连接过,就不用再连接。从“昆明”出发,应该与“贵阳”相连,虽然“贵阳”已经与“柳州”相连,但是仍然需要“昆明”与贵阳相连。如此一来,图中出现了若干个连为一体的城市集(例如“上海”“徐州”“郑州”“北京”四个城市被连为一体),然后对于每一个城市集,找出它们与其他城市集之间连接的成本最小线路。例如“上海”“徐州”“郑州”“北京”四个城市形成的城市集,与图中剩余5个城市形成的城市集之间,存在“郑州”——“成都”,“郑州”——“株洲”,“上海”——“株洲”。而我们要选择的是成本最小的“郑州”——“株洲”。就这样,直到所有城市连为一体。
上面说的方法①和方法②,都成功找出了图中的最优解。可是,这两种方法是否具有普适性,解决任意类似问题呢?
(答案提示中,是一个结论,这个结论是本题的关键)
A,B,C,D,E五人合作1天可以完成一项工程。已知A单独完成这项工程所需天数是B,C,D,E四人合作完成这项工程所需天数的2倍。B单独完成这项工程所需天数是A,C,D,E四人合作完成这项工程所需天数的3倍。C单独完成这项工程所需天数是A,B,D,E四人合作完成这项工程所需天数的4倍。D单独完成这项工程所需天数是A,B,C,E四人合作完成这项工程所需天数的5倍。问:这项工程由E单独完成,要多少天?