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

简要题意

在第 $1$ 行的城市中放最少的蓄水厂，（水向低处流）使第 $n$ 行的城市中全都有水流到。

特殊性分析

证明如果满足第 $n$ 行的城市中全都有水流到时，对于每个蓄水厂的水流到第 $n$ 行的城市中覆盖的范围是一个区间。

在下图的第 $4$ 行第 $3$ 列中没有水覆盖。

而因为在满足第 $n$ 行的城市中全都有水流到的这个条件，所以肯定有另几个蓄水厂能将水运到第 $4$ 行第 $3$ 列。 而另几个蓄水厂运水的路线肯定要穿过蓝色的路线（如下图）。

所以蓝色经过的路线就可以在蓝色与红色的交点处转弯，走红色的部分到达（如下图）。

所以猜想成立

思路

将每个蓄水厂所能覆盖到第 $n$ 行的区间记录下来（尝试在第 $1$ 行的每个位置都放蓄水厂），也就等同于记录在第 $n$ 行的每个城市能接收到哪几个蓄水厂的水。

因为我们需要最小化蓄水厂的数量，所以考虑贪心。

贪心方案：

对于在第 $n$ 行的每个城市来说，如果他能接收到的几个城市的蓄水厂中有已经确定要建蓄水厂的城市了那就不管他，否则建造从它开始覆盖长度最长的那个蓄水厂。

正确性证明：

如果已经可以收到确定建造的蓄水厂的水了，如果这时再建新的蓄水厂，这时的答案肯定更劣。

对于建造从它开始覆盖长度最长的那个蓄水厂的原因肯定就是显而易见的了。

code

如果你还是不明白，那就看下代码吧！

最终时间复杂度 $O(nm^{2})$。

#include<bits/stdc++.h>
using namespace std;
const int N=501;
vector<int> water[N];//在第 n 行第 i 列的城市有哪些在第 1 行蓄水厂的水可以到达。
//也就是在第 n 行第 i 列的城市能接收到水的蓄水厂编号的集合。
//例如 water[3]={1,2,4} 就表示在第 n 行第 3 列的城市能接收到在第 1 行第 1,2,4 列城市所建的蓄水厂的水
int mp[N][N],n,m,last[N];
bool vis[N][N],flag[N];
//flag[i] 表示第 1 行的第 i 列的城市是否确定要放蓄水厂 
struct node{
	int x,y,h;
};
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
    	if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
queue<node> q;
void bfs(int x){
	memset(vis,0,sizeof(vis));
	q.push({1,x,mp[1][x]});
	while(!q.empty()){
		int nx=q.front().x,ny=q.front().y,nh=q.front().h;
		q.pop();
        if(vis[nx][ny]) continue;
		vis[nx][ny]=1;
		if(nx==n) water[ny].push_back(x);//如果流到第 n 行了就记录这个城市可以收到哪些蓄水厂的水 
		if(nx+1<=n && mp[nx+1][ny]<nh) q.push({nx+1,ny,mp[nx+1][ny]}); //bfs 模拟水流。
		if(ny+1<=m && mp[nx][ny+1]<nh) q.push({nx,ny+1,mp[nx][ny+1]});
		if(nx-1>=1 && mp[nx-1][ny]<nh) q.push({nx-1,ny,mp[nx-1][ny]});
		if(ny-1>=1 && mp[nx][ny-1]<nh) q.push({nx,ny-1,mp[nx][ny-1]});
	}
}

int main(){
	cin>>n>>m;
	int ans=0,op_ans=1,ans2=0;
	for(register int i=1;i<=n;i++) for(int j=1;j<=m;j++) mp[i][j]=read();
	for(register int i=1;i<=m;i++) bfs(i);//尝试在第 1 行的第 i 列的城市上放蓄水厂 
	for(register int i=1;i<=m;i++) if(!water[i].size()) op_ans=0,ans2++;//如果在第 n 行有城市不能收到水就无解 
	if(!op_ans){
		cout<<0<<endl<<ans2;
		return 0;
	}
	for(register int i=1;i<=m;i++) for(int j=0;j<water[i].size();j++)last[water[i][j]]=i;//记录最后一次出现来判断覆盖的区间是否最大 
	for(register int i=1;i<=m;i++){
		bool flag2=0;
		for(register int j=0;j<water[i].size();j++)if(flag[water[i][j]]==1){flag2=1;break;}//已经有确定建造的了。
		if(flag2==0){//如果不包含确定建造的蓄水厂 
			ans++;
			int max_last=0,maxj=0;
			for(register int j=0;j<water[i].size();j++) if(last[water[i][j]]>max_last) max_last=last[water[i][j]],maxj=j;
			flag[water[i][maxj]]=1;//选择覆盖的区间最大的蓄水厂来建。
		}
	}
	cout<<1<<endl<<ans;
	return 0;
}

码字不易，给个赞吧QwQ。