【题目大意】
给定一个N*M(N,M<=500)的矩阵，矩阵中每一个格子都有一个权值。
1、只有第一行的格子能够建蓄水厂。
2、若与该格子有公共边的格子已经建有水利设施，并且这个建有水利设施的格子的权值大于该格子的权值，那么该格子可以建一个输水站。
问：能否使最后一行所有的点都建上水利设施？若能，则输出最少建多少个蓄水厂可以达到要求。若不能，则输出最后一行有多少个格子无法建立水利设施。
【算法分析】
首先注意到两个性质。
1、假设i,j都为第一行建蓄水厂的位置，那么他们供给最后一行的水利设施的配对关系可以不交叉。
如图：
若交叉，那么i必然能控制j现在控制的点。于是反证得该性质正确。
2、假设最后一行的每个点都能被覆盖，那么对于第一行的每一个结点，它所能控制最后一行的位置必然是连续的。
如图：
若不连续，根据性质1可知，其它点也无法覆盖红色部分，于是与“有解”这一前提矛盾，反证得该性质正确。
得出这两个性质以后解法就呼之欲出了。
首先把所有第一行的结点放入队列之中，进行广度优先搜索，然后可以看最后一行有多少个点被扩展到，从而得出是否有解以及有多少个点无法被覆盖到。
下面处理有解的情况。
对于每一个点，建立两个项L[i][j],R[i][j]，表示从这个点流出去，能覆盖到最后一行的最左端点及最右端点。
那么怎么快速处理得出所有点的L[i][j]及R[i][j]呢？
我们初始化所有L[N][i]=i , R[N][i]=i。
然后扩展开去影响其他的点。
笔者认为扩展有两类比较好的方法：
1、这个过程比较类似于最短路的扩展，所以SPFA或者Dijkstra+Heap都是不错的选择。使用它们的时间复杂度分别是O(kNM)、O(NM lg NM)
2、这个图显然是有向无环图，我们可以对它拓扑排序，然后按拓扑序扩展。这样做的时间复杂度O(NM)。或者说更直接一点按所有点的权值排序，然后按权值从小到大的顺序扩展。这样做的时间复杂度是O(NM lg NM)。
处理出所有的L[i][j]以及R[i][j]以后，问题就转化为：用最少的第一行的区间覆盖[1,M]这段所有的点。
令L’[i]=L[1][i]，R’[i]=R[1][i]。
我们按L’[i]把第一行的区间排序以后，就可以使用一个简单的贪心算法在O(M)的复杂度内解决这个问题。
这个贪心的C++代码如下，其中Q[i].L等价于L’[i],Q[i].R等价于R’[i]：
int MaxR=0,ans=0,tmp;
i=1;
while (MaxR tmp=MaxR; while (i<=m && Q[i].L<=MaxR+1) tmp=max(tmp,Q[i++].R); MaxR=tmp; ans++; } printf("%dn",ans); 【复杂度分析】 综上，我们如果在扩展时使用拓扑排序，那么可以做到 O(NM+M lg M)的时间复杂度 (这已经和读入数据所必须耗费的时间差不多了) O(NM )的空间复杂度