首页 > 代码库 > [bzoj4849][Neerc2016]Mole Tunnels

[bzoj4849][Neerc2016]Mole Tunnels

来自FallDream的博客,未经允许,请勿转载,谢谢


貌似是省队集训女队讲的题。。。

今天在bzoj找一道题无果,但是翻到了这道就顺便写了下。

 

鼹鼠们在底下开凿了n个洞,由n-1条隧道连接,对于任意的i>1,第i个洞都会和第i/2(取下整)个洞间有一条隧道,第i个洞内还有ci个食物能供最多ci只鼹鼠吃。一共有m只鼹鼠,第i只鼹鼠住在第pi个洞内,一天早晨,前k只鼹鼠醒来了,而后n-k只鼹鼠均在睡觉,前k只鼹鼠就开始觅食,最终他们都会到达某一个洞,使得所有洞的ci均大于等于该洞内醒着的鼹鼠个数,而且要求鼹鼠行动路径总长度最小。现对于所有的1<=k<=m,输出最小的鼹鼠行动路径的总长度,保证一定存在某种合法方案。
n<=10^5
 
看出是完全二叉树上费用流  建图比较简单 但是并不能过
发现树高是log级别的,所以考虑直接手动模拟。
f[x]表示从x走到子树中的一个可以觅食的点的最短距离,顺便记一下是哪个点。
一条边记一下它的正向通过次数和反向通过次数,如果他们相同那么两条边的距离都是1,不然有一个方向会因为反向边而变成-1
然后直接枚举lca更新答案,并且更新通过次数和f数组即可。
复杂度nlogn
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define MN 100000using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}    while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}    return x*f;}int n,m,p[MN+5],tms[MN+5],f[MN+5],From[MN+5],ans=0;inline int GetU(int x){return tms[x]<=0?1:-1;}inline int GetD(int x){return tms[x]>=0?1:-1;}void update(int x){    int l=x<<1,r=x<<1|1;    if(p[x]) f[x]=0,From[x]=x;    else    {        f[x]=1e9,From[x]=0;        if(l<=n&&f[l]+GetD(l)<f[x]) f[x]=f[l]+GetD(l),From[x]=From[l];        if(r<=n&&f[r]+GetD(r)<f[x]) f[x]=f[r]+GetD(r),From[x]=From[r];    }}int main(){    n=read();m=read();    for(int i=1;i<=n;++i) p[i]=read();    for(int i=n;i;--i) update(i);    for(int i=1;i<=m;++i)    {        int x=read(),mn=f[x],Best=x,d=0;        for(int t=x;t>1;t>>=1)            if(f[t>>1]+(d+=GetU(t))<mn)                mn=f[t>>1]+d,Best=t>>1;        printf("%d ",ans+=mn);--p[From[Best]];        for(int i=From[Best];i>Best;i>>=1)            ++tms[i],update(i);        for(int i=x;i>Best;i>>=1)            --tms[i],update(i);        for(int i=Best;i;i>>=1) update(i);    }    return 0;}

 

[bzoj4849][Neerc2016]Mole Tunnels