P1514 [NOIP 2010 提高组] 引水入城题解

· · 题解

题目传送门

更好的阅读体验？

题目大意

一个国家可以看做是一个 N \times M 的矩阵，每一个格子就是一个城市。现在要在第 1 行的城市中建蓄水厂，将水输送到第 N 行的每一个城市。水只能从海拔高的地方流向海拔低的地方。求最少要建造几个蓄水厂。

思路分析

对于每一个在第 1 行的城市，采用广度优先搜索，搜索如果在这里建蓄水厂，水能流向哪几个在第 N 行的城市，用标记数组记录。如果有在第 N 行的城市没办法收到水，则输出 0 和缺水城市的数量。

但是如果每一座城市都能收到水，至少该建几个蓄水厂呢？

定理

在有解的情况下，每个蓄水厂流到的第 N 行城市是个区间。

证明

假设图上绿色的城市建造蓄水厂，水从蓝色的路线流向最后一行的黄色城市。其中橙色城市没有收到水。此时，第 N 行城市中覆盖的范围不是个区间。

因为要保证题目一定有解，所以一定有第 1 行的一座城市能给橙色城市供水。图中红色城市能给橙色城市供水。

此时，绿色城市的供水路线与红色城市的供水路线存在着重叠，即图中深蓝色路线。而显然地，既然红色城市供的水能从深蓝色路线流向橙色城市，那么绿色城市供的水也可以。

因此，每个蓄水厂流到的第 N 行城市是个区间。

证毕。

既然每个蓄水厂流到的第 N 行城市是个区间，接下来就可以使用线段覆盖的方法解题。下文把 M 座城市看做一条长度为 M 的线段，每个蓄水厂流向的区间看做是一条条线段。

思路很简单，采用贪心，先设一个变量记录最大左端点，遍历每条线段的左端点与右端点。在左端点小于等于最大左端点的线段中选择右端点最大的一条线段，将最大左端点更新为这条线段的右端点，以此往复，直到最大左端点大于等于 M 即可。最后输出的线段数即为答案。

AC 代码

#include <bits/stdc++.h>
using namespace std;
struct city{ //蓄水厂，有水流向沙漠城市的左端点和右端点
    int st,en;
}cities[510];
int n,m,s[510][510],L=1,ans=0;
int dh[5]={0,-1,0,1,0};
int dl[5]={0,0,1,0,-1};
bool f[510][510][510],p[510];
void bfs(int r,int c,int j){ //广搜，搜索水能流向那几座城市
    queue<int> qx,qy;
    qx.push(r);
    qy.push(c);
    f[j][r][c]=true;
    if(n==1){
        p[c]=true;
    }
    while(!qx.empty()){
        int x=qx.front(),y=qy.front();
        qx.pop();
        qy.pop();
        for(int i=1;i<=4;i++){
            int dx=x+dh[i],dy=y+dl[i];
            if(dx>=1 && dx<=n && dy>=1 && dy<=m){
                if(!f[j][dx][dy] && s[dx][dy]<s[x][y]){
                    f[j][dx][dy]=true;
                    qx.push(dx);
                    qy.push(dy);
                    if(dx==n){
                        p[dy]=true; //标记数组，记录是不是每座沙漠城市都有水
                        cities[j].st=min(cities[j].st,dy); //因为一定是一个区间，所以直接统计左右端点
                        cities[j].en=max(cities[j].en,dy);
                    }
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>s[i][j];
        }
    }
    for(int i=1;i<=m;i++){
        cities[i].st=i;
        cities[i].en=i;
    }
    for(int i=1;i<=m;i++){
        bfs(1,i,i);
    }
    int city_num=0;
    for(int i=1;i<=m;i++){
        if(!p[i]){
            city_num++;
        }
    }
    if(city_num){ //有沙漠城市没有水
        cout<<"0\n"<<city_num;
        return 0;
    }
    cout<<"1\n";
    while(L<=m){ //线段覆盖
        int maxa=-1,maxn=-1e9;
        for(int i=1;i<=m;i++){
            if(cities[i].st<=L){
                if(cities[i].en>maxn){
                    maxa=i;
                    maxn=cities[i].en;
                }
            }
        }
        L=cities[maxa].en+1;
        ans++;
    }
    cout<<ans; //输出答案
    return 0;
}