首页 > 代码库 > 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