题解 P2266 【爱的供养】

shanjianyu · 2017-10-18 18:26:00 · 题解

本题要求求出和某个格子相连的最小边的最大值的最小值(变得权值可以看作为格子与格子之间高度的绝对值之差)，因此我们需要用最小生成树来解决，由于询问可能很多我们需要对答案进行预处理。

建图：我们可以将每个格子和它周围的格子连边，边权为格子高度绝对值之差，之后我们对整个图跑最小生成树。但是我们需要保证至少走过T个格子，我们用并查集维护联通性，还要维护每个集合里面的顶点数以及每个集合它所询问的点数，如果两个集合合并后它们的点数之和>= T，那么其中一个集合询问的点数就对答案有贡献，即ans+=ask[i]，ask[i]表示i集合有多少个询问的点(即里面包含多少个钥匙)，之后将两个集合合并。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
#define LL long long 
#define Maxn 400005
#define Maxm 1600005

struct node {
    LL u,v,w;
}e[2*Maxm];

LL n,m,T,cnt,N,tot,M,ans=0;
LL fa[Maxn],dot[Maxn],ask[Maxn],rank[Maxn];
LL a[605][605],b[605][605],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};

bool comp(const node &k1,const node &k2) {return k1.w<k2.w;}
LL find(LL x) {
    if(fa[x]==x) return x;
    else return fa[x]=find(fa[x]);
}

//ask[i]表示i集合询问的点数,dot[i]表示i集合里面的点数 
int main() {
    scanf("%lld%lld%lld",&n,&m,&T);N=n*m;
    for(int i=1;i<=n*m;i++) fa[i]=i,dot[i]=1;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%lld",&a[i][j]);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
        scanf("%lld",&b[i][j]);
        ask[(i-1)*m+j]=b[i][j];
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
        for(int k=0;k<4;k++) {
            int x=i+dx[k],y=j+dy[k];
            if(x>n||x<1||y<1||y>m) continue ;
            e[++M].u=(i-1)*m+j;e[M].v=(x-1)*m+y;
            e[M].w=abs(a[i][j]-a[x][y]);
        } 
    }
    sort(e+1,e+M+1,comp);LL r1,r2;
    for(int i=1;i<=M;i++) {
        r1=find(e[i].u);r2=find(e[i].v);
        if(r1!=r2) {
            if(dot[r1]+dot[r2]>=T) {
                if(dot[r1]<T) ans+=e[i].w*ask[r1]; 
                if(dot[r2]<T) ans+=e[i].w*ask[r2];//这两句话统计对答案的贡献    
            }    
            if(rank[r1]<rank[r2]) fa[r1]=r2,dot[r2]+=dot[r1],ask[r2]+=ask[r1];
            else {
                fa[r2]=r1,dot[r1]+=dot[r2],ask[r1]+=ask[r2];
                if(rank[r1]==rank[r2]) rank[r1]++;
            }
            tot++;
            if(tot==N-1) break;
        }
    } 
    printf("%lld\n",ans);
    return 0;
}