本文主要是介绍noip2010 引水入城 bfs+贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
如果能够实现，每个河边的城市对应的控制区域一定是一条线段。
所以直接bfs每个河边的城市，贪心线段的右端点
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int qx[500005],qy[500005],a[505][505],n,m,bo[505][505],ans;//队列一定要开大！！！！！！
bool flag[505],ff[505];
struct WATER{int l,r;WATER(){l=r=0x7fffffff;}
}ww[505];
void bfs(int xx){int h=1,t=1,x,y;qx[1]=1; qy[1]=xx;bo[1][xx]=xx;while(h<=t){x=qx[h]; y=qy[h++];if((x-1>0)&&(bo[x-1][y]!=xx)&&(a[x-1][y]<a[x][y])){qx[++t]=x-1;qy[t]=y;bo[x-1][y]=xx;}if((x+1<=n)&&(bo[x+1][y]!=xx)&&(a[x+1][y]<a[x][y])){qx[++t]=x+1;qy[t]=y;bo[x+1][y]=xx;}if((y-1>0)&&(bo[x][y-1]!=xx)&&(a[x][y-1]<a[x][y])){qx[++t]=x;qy[t]=y-1;bo[x][y-1]=xx;}if((y+1<=m)&&(bo[x][y+1]!=xx)&&(a[x][y+1]<a[x][y])){qx[++t]=x;qy[t]=y+1;bo[x][y+1]=xx;}}
}
bool cmp(WATER a,WATER b){if(a.l==b.l) return a.r<b.r;return a.l<b.l;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);for(int i=1;i<=m;i++){if(a[1][i-1]<=a[1][i]&&a[1][i+1]<=a[1][i]){bfs(i);for(int j=1;j<=m;j++){if(bo[n][j]==i){flag[j]=1;if(!ff[i]) ww[i].l=j,ff[i]=1;ww[i].r=j;}}} }for(int i=1;i<=m;i++)if(!flag[i])ans++;if(ans){printf("0\n%d\n",ans);return 0;}sort(ww+1,ww+m+1,cmp);int now=1,maxr=1,it=1,maxm=m;for(int i=1;i<=m;i++)if(ww[i].l>m){maxm=i-1;break;}while(now<m){maxr=now+1;for(int i=it;i<=maxm;i++){if(ww[i].l>now+1) break;if(ww[i].l<=now+1){if(ww[i].r>=maxr){maxr=ww[i].r;it=i;}}}now=maxr; ans++;}printf("1\n%d\n",ans);return 0;
}这篇关于noip2010 引水入城 bfs+贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
