首页 > 代码库 > BZOJ3485 : [Baltic2012]peaks
BZOJ3485 : [Baltic2012]peaks
首先将每个平原缩成一个点,建出图,相邻两个点之间的边权为它们高度的较小值。
用Kruskal算法求出这个图的最大生成树,每次合并两个连通块时新建一个点指向它们,得到一棵有根树。
对于每个点,求出它子树内最高的峰,那么对于每个叶子,在它到根的路径上二分查找即可。
时间复杂度$O(nm\log(nm))$。
#include<cstdio>#include<algorithm>using namespace std;const int N=2005,M=200010;int n,m,i,j,x,y,z,dx,dy,a[N][N],p[N][N],cb;int cnt,is[M],h[M],f[M],son[M][2],ma[M],q[M],top,ans;struct P{int x,y;P(){}P(int _x,int _y){x=_x,y=_y;}}b[M/2],fin[M/2];inline bool cmp(const P&x,const P&y){return a[x.x][x.y]>a[y.x][y.y];}inline bool cmp2(const P&a,const P&b){return a.x==b.x?a.y>b.y:a.x>b.x;}inline void read(int&a){char c;while(!(((c=getchar())>=‘0‘)&&(c<=‘9‘)));a=c-‘0‘;while(((c=getchar())>=‘0‘)&&(c<=‘9‘))(a*=10)+=c-‘0‘;}void dfs(int x,int y){ p[x][y]=cnt; for(int i=x-1;i<=x+1;i++)for(int j=y-1;j<=y+1;j++){ if(a[i][j]>a[x][y])is[cnt]=0; if(a[i][j]==a[x][y]&&!p[i][j])dfs(i,j); }}int F(int x){return f[x]==x?x:f[x]=F(f[x]);}inline void merge(int x,int y,int z){ if(!x||!y)return; x=F(x),y=F(y); if(x==y)return; h[++cnt]=z,f[cnt]=cnt; son[cnt][0]=x,son[cnt][1]=y; f[x]=f[y]=cnt;}void dfs2(int x){ if(is[x])ma[x]=h[x]; for(int i=0;i<2;i++){ int y=son[x][i]; if(!y)continue; dfs2(y); ma[x]=max(ma[x],ma[y]); }}inline void cal(int o){ int l=1,r=top,t=0,mid; while(l<=r)if(ma[q[mid=(l+r)>>1]]>o)l=(t=mid)+1;else r=mid-1; fin[++ans]=P(o,h[q[t]]);}void dfs3(int x){ if(is[x])cal(h[x]); q[++top]=x; for(int i=0;i<2;i++){ int y=son[x][i]; if(!y)continue; dfs3(y); } top--;}int main(){ read(n),read(m); for(i=1;i<=n;i++)for(j=1;j<=m;j++)read(a[i][j]); for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(!p[i][j])is[++cnt]=1,h[cnt]=a[i][j],dfs(i,j); for(i=1;i<=n;i++)for(j=1;j<=m;j++)b[++cb]=P(i,j); sort(b+1,b+cb+1,cmp); for(i=1;i<=cnt;i++)f[i]=i; for(i=1;i<=cb;i++){ x=b[i].x,y=b[i].y,z=p[x][y]; for(dx=x-1;dx<=x+1;dx++)for(dy=y-1;dy<=y+1;dy++)if(a[dx][dy]>=a[x][y])merge(p[dx][dy],z,a[x][y]); } dfs2(cnt),dfs3(cnt); sort(fin+1,fin+ans+1,cmp2); printf("%d\n",ans); for(i=1;i<=ans;i++)printf("%d %d\n",fin[i].x,fin[i].y); return 0;}
BZOJ3485 : [Baltic2012]peaks
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。