自动搬运

查看原文

来自洛谷，原作者为

	zengxr **

搬运于2025-08-24 21:45:19，当前版本为作者最后更新于2019-03-02 08:34:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

跟楼下大佬的做法都不一样

大致思路：

采用并查集巧妙联通

算法步骤：

1.先建立好图，每个点向右边点，下边点连边，权值为两者差的绝对值

2.将边权从小到大排序

3.不断加边进来，当合并的集合中点的个数>=T个， 则最新加入的边权*集合中有多少个出发点即为答案

4.然后则集合中出发点个数清零即可

代码：

#include<bits/stdc++.h>
using namespace std;
long long dx[3]={0, 1, 0}, dy[3]={0, 0, 1};
long long n, m, t;
long long cnt, tot;
long long ans;
struct node{
    long long x, y, dis;
}a[250005];
long long f[505][505];
long long father[250005],size[250005];
long long num[505][505],v[250005];
long long find(long long x)
{
  if(x!=father[x])
    father[x]=find(father[x]);
  return father[x];
}
bool cmp(node x,node y)
{
  return x.dis<y.dis;
}
int  main()
{
    for(int i=1;i<=250004;i++)
      size[i]=1,father[i]=i;
    scanf("%lld%lld%lld",&n,&m,&t);
    tot=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            scanf("%lld",&f[i][j]);
            tot+=1;
            num[i][j]=tot;
        }
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            int flag;
            scanf("%d",&flag);
            if(flag) v[num[i][j]]=1;
            for (int k=1;k<=2;k++)
            {
                int tx=i+dx[k],ty=j+dy[k];
                if (tx<n+1&&ty<m+1) a[++cnt]=(node){num[i][j],num[tx][ty],abs(f[i][j]-f[tx][ty])};
            }
        }
    }//建图
    sort(a+1,a+1+cnt,cmp);//排序
    for(int i=1;i<=cnt;i++)//不断加边
    {
        int x=a[i].x,y=a[i].y;
        int fx=find(x), fy=find(y);
        if(fx==fy)continue;
        if (size[fx]+size[fy]>=t)
        {
            if (size[fx]<t)ans+=a[i].dis*v[fx];
            if (size[fy]<t)ans+=a[i].dis*v[fy];
        }
        if (size[fx]>size[fy]) swap(fx,fy);
        father[fx]=fy;
        size[fy]+=size[fx],v[fy]+=v[fx];
    }
    printf("%lld",ans);//输出答案
    return 0;
}

提醒：要记得开long long