JZOJ 【BOI2012】Peaks

题意就不说了。

分析：一看就是经典套路，一般来讲思路就是先建图然后二分，然后细节比较多。

先把平原都缩点，不然会爆。然后因为让你求任意两个山峰之间的最小值最大，那就做kruskal最大生成树，然后每次合并的时候建一个新点，链接这两个块，然后注意边权是小的那个高度（最小值），这样搞出来就是一棵树，那么我们在每个叶子节点和根之间二分查找答案就行了。

我打的比较丑。。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int n,m;
const int N=e3+,M=e5+;
int x,y,z,dx,dy,a[N][N],p[N][N],tot;
int cnt,is[M],h[M],f[M],son[M][],mx[M],q[M],top;
int ans;
struct node
{
    int x,y;
}b[M],ans1[M];
inline bool cmp(node x,node y)
{
    return a[x.x][x.y]>a[y.x][y.y];
}
inline bool cmp2(node a,node b)
{
    return a.x==b.x?a.y>b.y:a.x>b.x;
}
inline void dfs(int x,int y)
{
    p[x][y]=cnt;
    fo(i,x-,x+)
    fo(j,y-,y+)
    {
        if (a[i][j]>a[x][y])is[cnt]=;
        if (a[i][j]==a[x][y]&&!p[i][j])dfs(i,j);
    }
}
inline int find(int x)
{
    if (f[x]==x)return x;
    else return f[x]=find(f[x]);
}
inline void merge(int x,int y,int z)
{
    if (!x||!y)return;
    x=find(x);
    y=find(y);
    if (x==y)return;
    h[++cnt]=z;
    f[cnt]=cnt;
    son[cnt][]=x;
    son[cnt][]=y;
    f[x]=f[y]=cnt;
}
inline void dfs1(int x)
{
    if (is[x])mx[x]=h[x];
    fo(i,,)
    {
        int v=son[x][i];
        if (v)
        {
            dfs1(v);
            mx[x]=max(mx[x],mx[v]);
        }
    }
}
inline void cal(int x)
{
    int l=,r=top;
    int t=;
    while (l<=r)
    {
        int mid=(l+r)/;
        if (mx[q[mid]]>x)
        {
            t=mid;
            l=mid+;
        }
        else r=mid-;
    }
    ans1[++ans].x=x;
    ans1[ans].y=h[q[t]];    
}
inline void dfs2(int x)
{
    if (is[x])cal(h[x]);
    q[++top]=x;
    fo(i,,)
    {
        int v=son[x][i];
        if (v)
        {
            dfs2(v);
        }
    }
    top--;
}
int main()
{
    //freopen("peaks.in", "r", stdin);  
    //freopen("peaks.out", "w", stdout);      
    scanf("%d%d",&n,&m);
    fo(i,,n)
    fo(j,,m)scanf("%d",&a[i][j]);
    fo(i,,n)
    fo(j,,m)if (!p[i][j])
    {
        is[++cnt]=;
        h[cnt]=a[i][j];
        dfs(i,j);
    }
    fo(i,,n)
    fo(j,,m)
    {
        b[++tot].x=i;
        b[tot].y=j;
    }
    sort(b+,b++tot,cmp);
    fo(i,,cnt)f[i]=i;
    fo(i,,tot)
    {
        x=b[i].x;
        y=b[i].y;
        z=p[x][y];
        fo(x1,x-,x+)
        fo(y1,y-,y+)
        if (a[x1][y1]>=a[x][y])
        merge(p[x1][y1],z,a[x][y]);
    }
    dfs1(cnt);
    dfs2(cnt);
    sort(ans1+,ans1++ans,cmp2);
    printf("%d\n",ans);
    fo(i,,ans)
    printf("%d %d\n",ans1[i].x,ans1[i].y);
    return ;
}