记录编号	97339	评测结果	AAAAAAAAAA
题目名称	[USACO Jan14]滑雪场地的难度系数	最终得分	100
用户昵称	Miku_lyt	是否通过	通过
代码语言	C++	运行时间	0.271 s
提交时间	2014-04-18 15:23:23	内存使用	11.32 MiB

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
const int maxn=250005,maxm=500005;
int n,m,T,N,M=0,h[505][505],num[505][505];
int x[maxm],y[maxm],z[maxm],fath[maxn],size[maxn],maxx[maxn];
bool root[maxm];
inline void _getnum(int &xx)
{
    char tt=getchar();
    while(tt<'0'||tt>'9')tt=getchar();
    for(xx=0;tt>='0'&&tt<='9';tt=getchar())xx=xx*10+(tt-'0');
}
inline int _abs(int number)
{
    if(number>=0)return number;
    else return 0-number;
}
void _qst(int l,int r)
{
    int i,j,m,t;
    i=l;j=r;
    m=z[(i+j)>>1];
    while(i<=j)
    {
        while(z[i]<m)i++;
        while(z[j]>m)j--;
        if(i<=j)
        {
            t=x[i];x[i]=x[j];x[j]=t;
            t=y[i];y[i]=y[j];y[j]=t;
            t=z[i];z[i]=z[j];z[j]=t;
            i++;j--;
        }
    }
    if(i<r)_qst(i,r);
    if(l<j)_qst(l,j);
}

inline int _getfath(int i)
{
    while(fath[i]!=i)i=fath[i];
    return i;
}

inline void _union(int X,int Y,int Z)  //将根为X,Y的两个并查集合并，这条边的权值为Z
{
    int t;
    if(size[X]>size[Y])t=X,X=Y,Y=t;   //让X是size较小的并查集
    fath[X]=Y;                        //将
    if(size[Y]<T&&size[X]+size[Y]>=T)maxx[Y]=Z;   //在新的根上记录答案。如果size[Y]<T，那么一定size[X]<T，把答案记在一起就好
    else if(size[X]<T&&size[X]+size[Y]>=T)maxx[X]=Z;   //这里不能把答案记录在Y上，因为Y上面可能已经记过某个答案
    size[Y]+=size[X];   //把size加起来。
}

inline long long _getmax(int i)
{
    while(i!=fath[i]&&maxx[i]==-1)i=fath[i];   //向上走到第一个记了答案的节点就返回。
    return (long long)(maxx[i]);
}

int main()
{
  freopen("skilevel.in","r",stdin);
  freopen("skilevel.out","w",stdout);

    int i,j,X,Y;
    long long ans=0;
    char tt;
    _getnum(n);_getnum(m);_getnum(T);
    N=n*m;
    for(i=1;i<=N;i++)
    {
        fath[i]=i;
        maxx[i]=-1;
        size[i]=1;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            _getnum(h[i][j]);
            num[i][j]=(i-1)*m+j;
        }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            tt=getchar();
            while(tt!='1'&&tt!='0')tt=getchar();
            if(tt=='1')root[num[i][j]]=true;
        }
    for(i=1;i<=n;i++)
        for(j=1;j<m;j++)
        {
            x[++M]=num[i][j];
            y[M]=num[i][j+1];
            z[M]=_abs(h[i][j]-h[i][j+1]);
        }
    for(i=1;i<n;i++)
        for(j=1;j<=m;j++)
        {
            x[++M]=num[i][j];
            y[M]=num[i+1][j];
            z[M]=_abs(h[i][j]-h[i+1][j]);
        }
    _qst(1,M);
    for(i=j=1;i<=M;i++)
    {
        X=_getfath(x[i]);
        Y=_getfath(y[i]);
        if(X!=Y)_union(X,Y,z[i]);
    }
    for(i=1;i<=N;i++)if(root[i]==true)ans+=_getmax(i);
    cout << ans << endl;
    return 0;
}