假如现在国家要进行一项工程,需要将图中9个城市用某种特殊缆线连接(只要任意两个城市之间都有至少一条通路即可,例如“北京”和“贵阳”,可以通过“北京”——“郑州”——“株洲”——“贵阳”连接起来)。
图中显示的是所有允许用缆线连接的城市以及连接的成本如图所示。
现在我们来讨论解决类似问题的方法。
①首先连接整幅图中成本最小的连接线,也就是“郑州”——“徐州”。之后把“郑州”和“徐州”看为一个整体,寻找其他城市中与他们之一相连成本最小的城市,也就是“徐州”——“上海”。然后将三个连接过的城市看为一个整体,找出其他城市与这三个城市之一连接成本最小的城市,也就是“北京”——“郑州”。就像这样,直到所有城市都连为一体。
②从每个城市出发,都有若干个允许连接的城市。首先对所有城市,连接它们与从它们出发允许连接的城市中连接成本最小的。例如从“郑州”出发,要连接“郑州”——“徐州”;从“贵阳”出发,要连接“贵阳”——“柳州”;从“柳州”出发,也要连接“贵阳”,但是已经连接过,就不用再连接。从“昆明”出发,应该与“贵阳”相连,虽然“贵阳”已经与“柳州”相连,但是仍然需要“昆明”与贵阳相连。如此一来,图中出现了若干个连为一体的城市集(例如“上海”“徐州”“郑州”“北京”四个城市被连为一体),然后对于每一个城市集,找出它们与其他城市集之间连接的成本最小线路。例如“上海”“徐州”“郑州”“北京”四个城市形成的城市集,与图中剩余5个城市形成的城市集之间,存在“郑州”——“成都”,“郑州”——“株洲”,“上海”——“株洲”。而我们要选择的是成本最小的“郑州”——“株洲”。就这样,直到所有城市连为一体。
上面说的方法①和方法②,都成功找出了图中的最优解。可是,这两种方法是否具有普适性,解决任意类似问题呢?
(答案提示中,是一个结论,这个结论是本题的关键)
[故事叙述]:公元2001年,1月2日,在A国A省A市A区,早上六点,公安局接到报警,清洁工李某说,本区的第一单元街上,一个下店上家,一楼开店二楼住宿平房小型餐厅内, 老板和老板娘死了,名字叫张大哥餐厅。
周警长,带领十名警员与相关人员,立案侦查,来到现场勘察,张某死在二楼1号房间的床上,1号房间的是关闭着没锁的, 王某死在房间外的走廊上,这是一个24小时营业的店,但是老板和老板娘,晚上到时间就睡觉或者在二楼休息。
由钱经理,带领其他员工继续值夜班,今天早上清洁工李某去二楼打扫卫生,才发现人死了,于是立刻报警。
[相关物证]:警察发现二楼死者张某隔壁2号房间的门是开着的,夫妻生的两岁半的孩子,在床上发烧,餐厅门口监控录像显示,昨晚只有1月1日早上八点,来应聘夜班的,赵某,昨天进去过二楼,找老板应聘厨师,死者现场留下的带血杀人刀,经鉴定就是这把刀杀的两名死者,刀把子上,检测出赵某的指纹,死者手机上,最后一通电话,通话记录是,与赵某的通话,时间是1月1日,晚上21点。
[法医验尸报告]:死者张某与死者王某,两人的死因是,被菜刀砍脖子至死,死亡时间是,1月2日凌晨一点到凌晨三点之间,胃中没有食物,没有中毒现象,没有别的疾病。
[房间结构]:下店上家,一楼是餐厅,带窗户就是那种让光进来白天省的开灯的设计,与厨房带窗户,一个侧所带窗户、所有窗户没上锁,十个桌子、20个椅子,2个冰箱、3个物品柜,2个灶具,大量食材,二楼一个侧所带窗户,1号房间和2号房间。
监控只能看到门外和直到一楼到上二楼那个楼梯。
[人物资料]:
张某40岁男,身高一米七,体重56公斤,B型血厅的老板,和老婆关系非要好
王某35岁女,身高一米七,体重54公斤,血型A,是张某的老婆,与老公关系非要好。
赵某26岁男,身高一米七,体重53公斤,血型B,赵某有盗窃前科自首,1千多个,追回98个,被判六年,盗窃金银器品,出狱1个月,没工作,有暴力倾向。
钱某34岁男,身高一米七,体重52公斤,血型B,餐厅的经理。
孙某30岁女,身高一米七,体重50公斤,血型B,餐厅的收银员。
冯某30岁男,身高一米八,体重60公斤,血型O,餐厅的服务员。
李某31岁男,身高一米八,体重60公斤,血型AB,餐厅的清洁工。
[人物口供]:
李某:今天早上六点,我去二层打扫卫生,发现人死了,所以立即报警,昨天凌晨左右忘记几点,好像是听到上面有一点动静,问了一问有事情吗,听到上面回复了一声没事,就没管了,没注意是不是老板的声音。
钱某:您好警察同志,坐下喝口茶,是这样昨天赵某应聘确实用过一把刀,现在不见了,所以应该凶器就是这把刀,当时比较忙,我就忘了把刀叫人收回去了,赵某可能直接给顺走了。
赵某:刀上有我的指纹是因为,我昨天应聘厨师时用的就是这把刀,昨天21点的电话是,张某说我休息一天之后,明天来上班,警察条子,老子他妈的没杀人呀,你他妈的不要认为我以前偷过东西,又来杀人了。
孙某:我是收银员,案发当时,我很忙什么也不知道,这事服务员冯某应该可以证明,小冯呀快过来和警察说说。
冯某:这事我能证明,孙某和我当时很忙的,孙某全程应该没时间去杀人,还有老板说下个月就要把这家餐厅给卖掉了。
A区公安局14天后,将案卷移交给A巿中级人民检查院复核,检察院认为证据不足,事实不清,决定不起诉赵某,无罪推定,赵某释放回家。
一个雨夜,警方接到了一位夫人的求救电话:“我在香槟街26号,有人要杀我。”警察回话时已经对方没有了声音,于是鹭警官火速前往报案地点,发现大门紧闭,警方破坏了大门进入室内,发现了门口的尸体,死者手部抓着手机,旁边还有一把手枪,死者腹内有一颗子弹,伤势非常严重,房内没有混乱和损毁,地板上只有死者的鞋印,死者上衣有被翻动的痕迹,另外警方还在死者家外栅栏前的花池中还发现了几个仓促的脚印已经栅栏附近散落的子弹壳。
警方调查认为与死者离婚不久的前夫有重大嫌疑,鹭警官赶往前夫家中发现他正要出门,“你前妻昨晚出事了你知道吗?”鹭警官问到, “我们已经离婚了并且我再也没去过她那里,她的死和我无关,我要去医院交钱!我的女儿得了重病!”男人急匆匆的回复。鹭警官拉住他,顺便审视了一下房间,破乱的房间里摆满了有些陈旧的马拉松、射击等冠军奖杯,似乎诉说着往日的辉煌。“你似乎很擅长运动啊”——“那是和她结婚时候的事,她很富有,所以我不用每日工作,空闲多了自然就会发展爱好,不过和她离婚我可没分到一分钱!现在我需要卖命的挣钱,多亏这个讨人厌的女人!”
鹭警官似乎明白了什么,看着他的眼睛——“你说谎,你就是凶手!”
警官说的对吗?