P3457 [POI2007]POW-The Flood

    • 135通过
    • 364提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 并查集 贪心 POI 2007 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB


  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示


    Description 你手头有一张该市的地图。这张地图是边长为 m∗n 的矩形,被划分为m∗n个1∗1的小正方形。对于每个小正方形,地图上已经标注了它的海拔高度以及它是否是该市的一个组成部分。地图上的所有部分都被水淹没了。并且,由于这张地图描绘的地面周围都被高山所环绕,洪水不可能自动向外排出。显然,我们没有必要抽干那些非该市的区域。




    以下 m 行,每行 n 个数,其绝对值表示相应格子的海拔高度;若该数为正,表示它是该市的一个区域;否则就不是。

    请大家注意:所有格子的海拔高度其绝对值不超过 1000 ,且可以为零.



    感谢@FlashHu 提供的翻译


    Byteburg, the capital of Byteotia, is a picturesque city situated in a valley in the midst of mountains. Unfortunately, recent heavy rainfall has caused a flood - all the Byteburg is now completely under water. Byteasar, the king of Byteotia, has summoned his most enlightened advisors, including you, to a council. After long deliberations the council agreed to bring a few pumps, set them up in the flooded area and drain Byteburg.

    The king has asked you to determine the minimum number of pumps sufficing to drain the city.

    You are provided with a map of the city and the valley it is situated in. The map is in the shape of a $m\times n$ rectangle, divided into unitary squares. For each such square the map tells its height above sea level and alsowhether it is a part of Byteburg or not. The whole area depicted in the map is under water. Furthermore, it issurrounded by much higher mountains, making the outflow of water impossible. Obviously, there is no needto drain the area that does not belong to Byteburg.

    Each pump can be placed in any unitary square depicted in the map. The pump will be drawing thewater until its square is completely drained. Of course, the communicating tubes principle makes its work, so draining one square results in lowering the water level or complete draining of those squares from which the water can flow down to the one with the pump. Water can flow only between squares with a common side (or, more exact, squares whose projections onto horizontal plane have a common side, since the squares may be at different level). Apart from that, the water obviously only flows down.


    Write a programme that:

    • reads description of the map from the standard input,

    • determines the minimum number of pumps needed to drain whole Byteburg,

    • writes out the outcome to the standard output.




    In the first line of the standard input there are two integers $m$ and $n$, separated by a single space, $1 \le n, m \le 1\ 000$. The following $m$ lines contain the description of the map. The $(i+1)$'th line describes the $i$'th row of unitary squares in the map. It contains $n$ integers $x_{i,1}, x_{i,2}, ..., x_{i_n}$, separated by single spaces,$-1\ 000 \le x_{i,j} \le 1\ 000$ ,$x_{i,j} \ne 1000$ . The number $x_{i,j}$ describes the $j$'th square of the $i$'th line. The ground level in this square is $|x_{i,j}|$ above sea level. If $x_{i,j} > 0$, then the square is part of Byteburg, otherwise it is outside the city. Notice, that the area of Byteburg need not be connected. In fact the city may have several separate parts.


    Your programme should write out one integer to the standard output - the minimum number of pumpsneeded to drain Byteburg.


    输入样例#1: 复制
    6 9
    -2 -2 -1 -1 -2 -2 -2 -12 -3
    -2 1 -1 2 -8 -12 2 -12 -12
    -5 3 1 1 -12 4 -6 2 -2
    -5 -2 -2 2 -12 -3 4 -3 -1
    -5 -6 -2 2 -12 5 6 2 -1
    -4 -8 -8 -10 -12 -8 -6 -6 -4
    输出样例#1: 复制