loj2876 水壶 [JOISC 2014 Day2] kruscal重构树

时间：2021-06-28 19:10:42

正解:kruscal重构树+bfs

解题报告:

我永远喜欢loj!

感觉这题和这题挺像的,,,预处理和解题方法都是,,,所以大概整体二分能过去?

但因为做这题主要是入门一下kruscal重构树,,,所以还是港kruscal重构树滴解法好了QAQ

首先先说下预处理趴,就怎么知道每个点的水壶大小是多少

这个显然就和我放的链接那题差不多,只是这个是四联通bfs

umm还是说下具体细节趴,,,还是有点儿区别来着QwQ

就对每个点记录离它最近的建筑的编号和距离,然后再拓展到别的建筑的时候就可以连起这两个建筑了

然后就成了kruscal板子了,,,?

就欧克了鸭QwQ

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define sc second

#define il inline

#define gc getchar()

#define mp make_pair

#define pb push_back

#define t(i) edge[i].to

#define ri register int

#define rc register char

#define rb register bool

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=+,M=+;

int h,w,p,q,nod_cnt,bl[N][N],dis[N][N],mv_x[]={,,,-},mv_y[]={,-,,},fa[M<<],fat[M<<][],ed_cnt,wei[M<<],dep[M<<],head[M<<];

char g[N][N];

struct ed{int to,nxt;}edge[M<<];

pair<int,int>city[M];

vector< pair<int,int> >E[N*N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void bfs()

{

    queue< pair<int,int> >Q;

    rp(i,,p)Q.push(city[i]),bl[city[i].fi][city[i].sc]=i;

    while(!Q.empty())

    {

        pair<int,int>nw=Q.front();Q.pop();

        rp(i,,)

        {

            pair<int,int>to=mp(nw.fi+mv_x[i],nw.sc+mv_y[i]);

            if(g[to.fi][to.sc]=='#' || to.fi< || to.sc< || to.fi>h || to.sc>w)continue;

            if(!bl[to.fi][to.sc])Q.push(to),bl[to.fi][to.sc]=bl[nw.fi][nw.sc],dis[to.fi][to.sc]=dis[nw.fi][nw.sc]+;

            else E[dis[to.fi][to.sc]+dis[nw.fi][nw.sc]].pb(mp(bl[to.fi][to.sc],bl[nw.fi][nw.sc]));

        }

    }

}

il void ad(ri y,ri x){edge[++ed_cnt]=(ed){x,head[y]};head[y]=ed_cnt;}

int fd(ri x){return fa[x]==x?x:fa[x]=fd(fa[x]);}

il void kruscal()

{

    rp(i,,p)fa[i]=i;nod_cnt=p;

    rp(i,,h*w)

    {

        for(auto j:E[i])

        {

            ri x=fd(j.fi),y=fd(j.sc);if(x==y)continue;

            ++nod_cnt;fa[nod_cnt]=fa[x]=fa[y]=nod_cnt;wei[nod_cnt]=i;ad(fat[x][]=nod_cnt,x);ad(fat[y][]=nod_cnt,y);

        }

    }

    rp(i,,)rp(j,,nod_cnt)fat[j][i]=fat[fat[j][i-]][i-];

}

void dfs(ri x){dep[x]=dep[fat[x][]]+;e(i,x)dfs(t(i));}

il int lca(ri x,ri y)

{

    if(dep[x]<dep[y])swap(x,y);

    my(i,,)if(dep[fat[x][i]]>=dep[y])x=fat[x][i];

    if(x==y)return x;

    my(i,,)if(fat[x][i]!=fat[y][i])x=fat[x][i],y=fat[y][i];

    return fat[x][];

}

int main()

{

//    freopen(".in","r",stdin);freopen(".out","w",stdout);

    h=read();w=read();p=read();q=read();rp(i,,h)scanf("%s",g[i]+);rp(i,,p)city[i].fi=read(),city[i].sc=read();

    bfs();kruscal();my(i,nod_cnt,)if(!dep[i])dfs(i);

    while(q--)

    {

        ri x=read(),y=read();if(fd(x)!=fd(y))printf("-1\n");else printf("%d\n",wei[lca(x,y)]);

    }

    return ;

}

放下代码QwQ

相关文章