汗，这个太霸气了，全部A掉。

最近还是有点忙的，今天要焊板子，我了个擦哟。

晚上回去拜读你的代码，哇哈哈。

有时间可以组团去刷嘛，哈哈，我很喜欢团体活动

[ 本帖最后由 demonleer 于 2012-8-20 13:42 编辑 ]

从代码揣摩作者的想法不是件容易的事情。我简单说说我的算法思想吧。

首先要做的工作都是一样的，要知道在某个滨湖城市建蓄水厂后能灌溉哪些沙漠城市。这个过程无非就是搜索（BFS、DFS），只要做好去冗工作，看来针对这个问题的测试示例，两者的效率并没有什么明显的区别。

我用的是DFS，就是那个flood函数。全局数组lr、lc充当搜索队列的角色，因为尺寸太大就放外面了。这本是针对多组数据测试方案安排的。

下一步就是计算最少用多少个蓄水厂了。关于这里的计算我的理论基础为如下一组结论。

1.如果某个蓄水厂可以灌溉到所有沙漠城市，那么结果为最少需要建1个蓄水厂，结束计算。

2.如果某个滨湖城市修建蓄水厂后可以灌溉到另一个滨湖城市，那这另一个滨湖城市没有修建蓄水厂的必要，跳过对该城市的搜索。

3.最关键的结论，如果前k个蓄水厂的最小覆盖子集为G，那么加入第k+1个蓄水厂后的最小覆盖子集|G'| = |G| + 1 - 冗余结点数。

因为，G是加入k+1前的最小覆盖子集，所以其中不存在冗余结点。当加入k+1之后，造成的冗余部分只与k+1相关，与k+1相关的冗余结点之间并不存在关联关系，所以可以直接删除。这一点很好理解，但证明起来不太容易，我的证明过程也不完备，就不写了。

完成这个计算过程的代码即analyze最后那段嵌套循环。

呵呵 最近几日白天有点事情，就晚上能上来学习下 ，看到各位这么热心参与并给俺看了这么多的代码和解题思路
真是又惊又喜啊
杨大哥说pk 哈哈 真想有那么一天啊 。只是现在俺的水平还很低 不够您一招就会趴下了 ，不过俺会努力争取以后
能接你三四招。

宝剑赠英雄，红粉送佳人。

只要是真心交流，我从不吝惜自己这点知识。

尺有所短，寸有所长。

pk只为营造一个积极热烈的气氛。胜，得到的是赞赏；败，得到的是鼓励和从胜利者那里吸收的知识。这不是挺好么？这样的失败不丢脸

刚看了杨大哥的代码。我不会的那部分，在你的代码里只有那么几行。另一个代码还没看，看这意思只是搜索的那部分不太一样喽？
这里原来能用上图论的理论。最小覆盖和最大匹配问题，我以前学图论的时候还学过一些，不过看来理论和应用之间距离还是比较远。要想搞算法，不集中学点知识是不行的了。

杨大哥要是有组队刷题的想法，我也愿意出点力。至少提不起你兴趣的题，我应该还是能解决的。

呵呵，兄弟谦虚了。说组团刷题其实主要是想和大家一起做点事情，找点乐子而已。以娱乐为主，然后寓教于乐，从中学点东西。

这个想法和这里很多初学者求拜师找学习群性质是一样的。人多比较有意思些，学习也就不那么枯燥了。

大家都太猛了，拜读

看完小施的代码后，必须要承认小施的算法比我的更优秀。

我的算法基于一个相对通用的结论，而小施的算法针对题目中图的特点使用了更强的结论，所以算法结构更简单，速度更快。

本来应该等小施自己来解释的，可他在焊板子，我就越俎代庖了。这里只说小施的算法理论中更强的那部分结论。

为了方便表述，我将滨湖城市结点称为L(lakeside)，将沙漠城市结点称为D(desert)。

1.如果L的子集可以覆盖D，则每个L结点所覆盖的D结点必定相邻可以连成一条线段。

2.如果L的子集可以覆盖D，则右侧的L结点所覆盖的D线段的左端，不可能超过左侧的L结点所覆盖的D线段的左端。

这两条结论可以用反证法证明。这应该已经到拓扑学的范畴了。

正是基于这两条结论，小施的算法才可以只通过一遍扫描即得出结果。很棒。

以上是我的观点，很愿意听小施自己解释一下算法的构建基础过程。

哈哈，能得到杨大哥的肯定，真是我的荣幸。

我的代码里最精华的两个函数应该就算是find_target和find_perfect了。

find_target这个函数的作用就是寻找合适的lakeside城市，所谓的合适就是该城市L左边和右边的海拔都比L自己低。我只把这些城市当作目标。

算法核心是find_answer这个函数，这个函数的作用是从find_target寻找到的目标开始遍历整个图，看看这个目标能覆盖多少沙漠城市D(desert)，并且用scope来记录这个L覆盖的范围，即从哪个城市到哪个城市。

这里有个非常重要的结论，也就是杨大哥所说的：

举个例子，如果某个L所能覆盖的范围是1,2,4,5,6这5个城市，那么其他的任何一个滨湖城市是不可能覆盖到3这个城市的，为什么呢？因为水流是连续的，既然水流已经通过某些途径覆盖了2和4这两个城市，那么3这个城市已经被包围起来了，其他的滨湖城市是不可能覆盖到3这个城市的，并且L右边的下一个滨湖城市所能覆盖到最左边的沙漠城市不可能比L所能覆盖的最左边的沙漠城市更左，因为水流是连续的，L右边的水流都能流过去，那么必然跟L的水流是有交点的，即则右侧的L结点所覆盖的D线段的左端，不可能超过左侧的L结点所覆盖的D线段的左端。

所以，在结果中，我先是调用find_result这个函数，来确认是否是有没有被覆盖到的城市，如果有则统计个数，然后打印结果，结束程序。
如果每个沙漠城市都能被覆盖，那么每个L的覆盖结果必然是连续的，即每个L结点所覆盖的D结点必定相邻可以连成一条线段。那么就调用find_perfect这个函数，这个函数是来统计最少的城市个数的。

如何来统计呢？大家仔细阅读find_perfect这个函数就能找到答案。

再次感谢杨大哥阅读我的代码。

下午又要继续焊板子，苦逼啊，我了个擦的。