4.20四川芦山地震发生后,抗震救灾委员会接到一个紧急任务,四川省给
该委员会发了一份地图,这份地图给出了该省一些城市的情况:任两个城市是
用一条或多条公路连接起来的,也可以没有公路连接,但是每个城市都可以直
接或间接地到达另外的城市,注意这些公路是可以双向行驶的。由于最近余震、
暴雨造成泥石流倾泻,使得车辆在这些公路上行驶很不安全,于是四川省决定
尽快对部分公路进行抢修,以保障救援车辆行车安全。
该省对所有的公路情况都进行了勘察,分析估计了抢修某段公路所需要花
费的时间,并记录在地图中。现在该省希望抗震救灾委员会能找到一个方案,
该方案决定出哪些公路需要抢修,使得抢修后的公路仍能保证任意两个城市之
间都能直接或间接地相连,同时为了安全起见,即使某一条抢修的公路被泥石
流阻断了,任意两城市仍能保持这个性质。由于时间紧迫,抗震救灾委员会还
需保证找到的这个方案总抢修时间最短。