NOIP2010提高组解题报告——Flow

【题目大意】

给定一个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       )的空间复杂度

留下评论

您的电子邮箱地址不会被公开。