专栏文章

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

hhexuchen
P1514题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipmmo80
此快照首次捕获于
2025/12/03 14:29
3 个月前
此快照最后确认于
2025/12/03 14:29
3 个月前
查看原文
题目传送门
更好的阅读体验？

题目大意

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

思路分析

对于每一个在第 11 行的城市，采用广度优先搜索，搜索如果在这里建蓄水厂，水能流向哪几个在第 NN 行的城市，用标记数组记录。如果有在第 NN 行的城市没办法收到水，则输出 00 和缺水城市的数量。
但是如果每一座城市都能收到水，至少该建几个蓄水厂呢？

定理

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

证明

假设图上绿色的城市建造蓄水厂，水从蓝色的路线流向最后一行的黄色城市。其中橙色城市没有收到水。此时，第 NN 行城市中覆盖的范围不是个区间。
因为要保证题目一定有解，所以一定有第 11 行的一座城市能给橙色城市供水。图中红色城市能给橙色城市供水。
此时，绿色城市的供水路线与红色城市的供水路线存在着重叠，即图中深蓝色路线。而显然地，既然红色城市供的水能从深蓝色路线流向橙色城市，那么绿色城市供的水也可以。
因此，每个蓄水厂流到的第 NN 行城市是个区间。
证毕。
既然每个蓄水厂流到的第 NN 行城市是个区间，接下来就可以使用线段覆盖的方法解题。下文把 MM 座城市看做一条长度为 MM 的线段，每个蓄水厂流向的区间看做是一条条线段。
思路很简单，采用贪心，先设一个变量记录最大左端点，遍历每条线段的左端点与右端点。在左端点小于等于最大左端点的线段中选择右端点最大的一条线段，将最大左端点更新为这条线段的右端点，以此往复，直到最大左端点大于等于 MM 即可。最后输出的线段数即为答案。

AC 代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...