题解 P1514 【引水入城】

思路各位大佬讲的都很明白了 蒟蒻就补个证明帮大家理理思路吧 [摘自 ~~大大大蒟蒻~~我の博客](https://www.cnblogs.com/Tony-Double-Sky/p/9871976.html) --- 欲证： 对于第一行的每个水库 $x_{i}$ 流出的水， 他能覆盖的最后一行情况必然是一个**连续的区间** 反证法： 假设存在一种情况使得覆盖情况如下， 覆盖不连续：  假设蓝色覆盖路线如下：  因为右边红色被覆盖了， 所以从红色水库到下方必然有一条路径  发现路径必有交（紫色部分）， 所以红色水库的水也会流入蓝色那部分， 假设不成立 故一座水库能覆盖的最后一行必然是一个**连续的区间** 证毕。 [全文](https://www.cnblogs.com/Tony-Double-Sky/p/9871976.html) ### upd 2019.11.11 我已经退役啦， 看到评论说的的， 证明确实有不足， 这里进行补充 引用评论区@Asurudo：（感谢这位小伙伴） @Asurudo ：“如果蓝色那部分干旱区很高，没有水流可以流到，则红色的水流可分叉。有一个样例就是这种情况，如果用这个结论去把区间当作连续的做，则红色可以流到本来流不到的地方。所以用此结论的前提是干旱区都能流到，否则不能用！” --- S9咱又夺冠啦！希望我高考也能顺利哈。