纯除草…… 最近被POI虐翻了…… 从POI10做到POI05，被虐的失去兴趣了…… 于是回POJ玩 >_<
原题地址 http://poj.org/problem?id=3242
题意比较麻烦…… 给定一个\(N*M\) ( \(1\leq N,M\leq 1000\) ) 的 Water Fence…… 每个格子都有一个介于1和N*M之间的初始高度h，任意两个格子高度都不同…… 然后Farmer John某天无聊往这个东西上头倒水…… 倒水的操作可以用pour(i,j,k)表示。 pour(i,j,k)表示往格子(i,j)上倒k立方单位的水（每个格子底面积都是1平方单位），然后水是慢慢倒下去的，一旦这个格子的水面高度高于周围的格子了，水就会因为物理原因流下去…… 如果某个瞬间这个格子水位同时比周围4个格子中的x个格子要高，高出来的这部分水就会平均分成x份，然后往比它低的每个格子流一份水。如果水流出了边界，那就视为浪费了，流进了无底洞，再也不会流回来。
现在FJ进行了不超过10^5次操作，问你最后浪费了多少水。
题解：
首先…… 要想到实时维护water fence 的情况显然不可行…… 一个有用的性质就是注意到最后结果是和操作次序无关的…… 这样题目就可做一点了…… 首把每个格子最终灌进了多少水算出来……
然后考虑一个个能积水的“水坑”，并用这个水坑的最高的柱子作为代表，这个也不难…… 就是首先整个图是空的，边界点就是周围一圈，从低到高加点，然后如果一个点和边界相邻，那么就floodfill，可达的点都是一个水坑的，并且把到达的点都设置为新的边界点。在纸上画画就能明白了…… 定义一个水坑的高度为这个水坑最高的柱子的高度，则可以发现水坑有明显的阶段性，高度低的水坑永远不会流到高度高的水坑……
所以按照代表柱子的高度从高往低处理水坑…… 一个水坑的最高的柱子的周围4个格子可能有几种情况：
1.属于另一个水坑，且比当前水坑高。这种情况显然水永远不可能流过去。
2.属于另一个水坑，且比当前水坑低。这种情况显然水能流进去，且一旦流进去就进了另一个更低的水坑，再也不会回来了（即使下面的水坑溢出也只会往更低的水坑流，而不会流回来）。
3.属于当前水坑。这样的话就floodfill把这个水坑里包含这个格子的连通块找出来…… 然后算出这个连通块的容量……
显然一个水坑最多能出现4个连通块…… 对于第三种情况算出每个连通块有多少个“入口“（与最高的格子相邻的格子个数），也就能分到多少份水，然后第二种情况每个格子都能分到一份水…… 所以模拟倒水，如果一个连通块分到的水超过容量，那么这个连通块被灌满了，删除这个连通块，多余的水先留着。否则把这些水全部灌进去，更新剩余容量。这样每次操作都能至少删掉一个连通块，反复执行这个过程，直到连通块被删光或水流光过程即结束，总时间复杂度是线性的。 注意很多细节要判…… 这样就可以过了。
其实这道题用到的算法只是最简单的floodfill而已…… 但本题只有16个人AC（目前）。这正是思路题的有趣之处吧，观察到重要的性质，想到正确的算法就不难了，否则就无从下手。
代码：https://ideone.com/xW2HX