如题32图所示为一个地区的交通网,顶点表示城市,边表示连接城市间的公路,边上的权值表示修建公路需花费的造价。现在需要选择能够连通每个城市且总造价最省的5条公路,请画出修建公路的方案,并给出该工程的总造价。
(1)该工程只有一种可能的方案: 
(注:每条边1分。)
(2)该工程的总造价为:10+2+7+6+10=35
如题32图所示为一个地区的交通网,顶点表示城市,边表示连接城市间的公路,边上的权值表示修建公路需花费的造价。现在需要选择能够连通每个城市且总造价最省的5条公路,请画出修建公路的方案,并给出该工程的总造价。
如题32图所示为一个地区的交通网,顶点表示城市,边表示连接城市间的公路,边上的权值表示修建公路需花费的造价。现在需要选择能够连通每个城市且总造价最省的5条公路,请画出修建公路的方案,并给出该工程的总造价。
(1)该工程只有一种可能的方案:
(注:每条边1分。)
(2)该工程的总造价为:10+2+7+6+10=35
