一道很好想的的贪心
但证明却不是那么容易 下面引一段周源大牛当年的解法以及证明 证的非常完美


周源:

贪心算法,也可以说成是构造算法吧,证明是我自己写的,应该是对的吧。

本题可以理解为,给定顶点数N和每个定点的度,要求构造一个满足要求的简单图。构造算法是这样的:为了叙述方便,我们每次选择剩余度数最大的点A(这是无所谓的,但是如果选择最大的点,算法描述和证明要简单一些)。让这个点依次和度数次大,第3大……的点连线,如果最终不够连了,那么显然无解,否则连完之后,该点就可以不考虑了,然后继续子问题的求解……,直到构造出解或者得到无解。

证明:设在某步构造的时候,将AB连线,但是已知解中,A,B间却没有连线,相反的,A,C之间却有边相连,且D(B)>D(C) D表示定点的度),正因为如此,一定至少有一个点Z满足ZB之间有边但是与C却没有边,这样,将A,C边改为C,ZB,Z边改为A,B仍然满足条件,于是也满足算法的要求,可以被算法构造出来。


posted on 2009-03-20 01:52 250 阅读(251) 评论(1)  编辑 收藏 引用

FeedBack:
# re: 100book 0006
2009-05-10 12:44 | JackDavid127
什么是100book?  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年3月>
22232425262728
1234567
891011121314
15161718192021
22232425262728
2930311234

留言簿(6)

随笔分类

随笔档案

文章档案

相册

搜索

  •  

最新评论