题解 P1514 【引水入城】

这次不说闲话了，直接怼题 ------ 这道题用bfs其实并不难想，但比较困难的是怎么解决满足要求时输出蓄水厂的数量。其实就像其他题解说的那样，我们可以用bfs将它转化成一个区间覆盖问题，然后再进行贪心。 首先枚举每个靠近湖泊的城市，假设它建有蓄水站，然后从它开始广搜，搜到最后一行，也就靠近沙漠的城市后，记录能建输水站的一个区间。可能有人会问：如果一个蓄水站搜到的最后一行的区间不止一截，可能有多截怎么办呢？ 我们可以这么思考：如果它有多截，那么每截中间肯定夹着一个(或一片)海拔比较高的城市，而且这个(片)城市的四面八方的海拔都比它小，那么这就是无解的，那一个(片)城市是无法建造输水站的。 我们在搜到最后一行时，记录下能被搜到的城市，在全部搜完后，我们再扫一遍记录的数组，如果都能被搜到，我们就用贪心去找最少的蓄水站，如果有城市是干旱区，那就很好处理了，输出无解+没被扫到的城市数量 代码： ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int read() //快读 { short int k=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) k=k*10+c-48; return k*f; } int vis[501][501]; int mapp[501][501]; //记录地图+寻找区间 struct zzz{ int x, y; }q[500*500+10]; int h=1,t; //搜索队列 struct hhh{ int f, t; }xd[1001]; int tot; //记录区间 bool cmp(hhh x,hhh y) //sort自定义比较函数 { if(x.f!=y.f) return x.f<y.f; else return x.t>y.t; } // 存四个方向 int fx[5]={0,1,0,-1,0}; int fy[5]={0,0,1,0,-1}; bool rqy[1001]; //存最后一行的城市是否被搜到过(听说用神犇的名字做变量会RP++) int n,m; int main() { //======输入 cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>mapp[i][j]; //======搜索 for(int i=1;i<=m;i++) { if(vis[1][i]) //这里用了一个剪枝:如果靠近湖泊的城市海拔较高,那么从这建一个蓄水站, //旁边靠近湖泊的城市就不用再建蓄水站了,直接建输水站就行了, //也就是说只要搜那海拔高的一个,就相当于把他周围的海拔低的能建蓄水站的城市全搜过了 continue; memset(vis,0,sizeof(vis)); h=1; t=0; q[++t].x=1, q[t].y=i; vis[1][i]=i; if(n==1) //特别处理一下n=1时的测试点 rqy[i]=1; while(h<=t) //搜索主体 { for(int j=1;j<=4;j++) { int xx=q[h].x+fx[j],yy=q[h].y+fy[j]; if(xx<=0||yy<=0||xx>n||yy>m) continue; if(!vis[xx][yy]&&mapp[q[h].x][q[h].y]>mapp[xx][yy]) { q[++t].x=xx; q[t].y=yy; vis[xx][yy]=i; if(xx==n) rqy[yy]=1; } } h++; } //===记录区间 bool www=0; for(int j=1;j<=m+1;j++) { if(vis[n][j]&&!www) { xd[++tot].f=j; www=1; } if(www&&!vis[n][j]) { xd[tot].t=j; break; } } } //======看每个城市能否被搜到 int jjj=0; for(int i=1;i<=m;i++) if(rqy[i]) jjj++; //如果不能全搜到 if(jjj!=m) { cout<<0<<endl<<m-jjj; return 0; } //可以全搜到,贪心线段覆盖 sort(xd+1,xd+tot+1,cmp); int now=0,to=0,ans=0; for(int i=1;i<=tot-1;i++) { if(now>=xd[i].f) to=max(xd[i].t,to); else { ans++; now=to; to=max(to,xd[i].t); } } cout<<1<<endl<<ans; return 0; } ```