首页 > 代码库 > 【BZOJ4849】[Neerc2016]Mole Tunnels 模拟费用流
【BZOJ4849】[Neerc2016]Mole Tunnels 模拟费用流
【BZOJ4849】[Neerc2016]Mole Tunnels
Description
鼹鼠们在底下开凿了n个洞，由n-1条隧道连接，对于任意的i>1，第i个洞都会和第i/2（取下整）个洞间有一条隧道，第i个洞内还有ci个食物能供最多ci只鼹鼠吃。一共有m只鼹鼠，第i只鼹鼠住在第pi个洞内，一天早晨，前k只鼹鼠醒来了，而后n-k只鼹鼠均在睡觉，前k只鼹鼠就开始觅食，最终他们都会到达某一个洞，使得所有洞的ci均大于等于该洞内醒着的鼹鼠个数，而且要求鼹鼠行动路径总长度最小。现对于所有的1<=k<=m，输出最小的鼹鼠行动路径的总长度，保证一定存在某种合法方案。
Input
第一行两个数n,m（1<=n,m<=100000)，表示有n个洞，m只鼹鼠。
第二行n个整数ci表示第i个洞的食物数。
第三行m个整数pi表示第i只鼹鼠所在洞pi。
Output
输出一行m个整数，第i个整数表示当k=i时最小的鼹鼠行动路径总长度。
Sample Input
5 4 0 0 4 1 1 2 4 5 2
Sample Output
1 1 2 4
题解：一眼看到这道题，直接想到费用流，但是n太大了，不能直接跑费用流，但是我们发现题中给的是一棵完全二叉树，所以我们可以想一想怎么利用这个性质。
我们依旧沿用费用流的思想，假设我们扫到了第i只鼹鼠，我们先找到距离i最近的有空位置的点，然后在将那个点的剩余空间-1，再讲路径上所有的反向边流量+1（因为正向边的流量可以看做正无穷，所以我们不管）。现在我们的思路就很清晰了，所以我们只要找到距离i最近的有空位置的点就行了。
具体做法是先扫一遍整棵树，用f[i]表示在i的子树中距离i最近的点到i的距离，g[i]表示在i的子树中距离i最近的点的位置。查询的时候，从p[i]一步一步向上爬，不断用当前节点的 f值+爬上来的距离 更新答案，最后暴力重构路径上的所有节点的f,g值，因为保证是完全二叉树，所以复杂度是O(nlogn)的。
说着挺容易其实代码挺丑的~
#include <cstdio> #include <cstring> #include <iostream> #define lson x<<1 #define rson x<<1|1 using namespace std; const int maxn=100010; typedef long long ll; ll ans; int n,m,sum,minn,pos,lca; int p[maxn],c[maxn],g[maxn],f[maxn],v[maxn][2]; //0上1下 int main() { scanf("%d%d",&n,&m); int i,j; for(i=1;i<=n;i++) scanf("%d",&c[i]); memset(f,0x3f,sizeof(f)); for(i=n;i>=1;i--) { if(c[i]) f[i]=0,g[i]=i; if(f[i>>1]>f[i]+1) f[i>>1]=f[i]+1,g[i>>1]=g[i]; } for(i=1;i<=m;i++) { scanf("%d",&p[i]); minn=1<<30,sum=0; for(j=p[i];j;j>>=1) { if(f[j]+sum<minn) minn=f[j]+sum,pos=g[j],lca=j; sum+=(v[j][0]>0)?(-1):1; } ans=ans+minn; printf("%lld",ans); if(i!=m) printf(" "); c[pos]--; for(j=p[i];j!=lca;j>>=1) v[j][0]?v[j][0]--:v[j][1]++; for(j=pos;j!=lca;j>>=1) v[j][1]?v[j][1]--:v[j][0]++; for(j=p[i];j!=lca;j>>=1) { f[j]=1<<30; if(c[j]&&0<f[j]) f[j]=0,g[j]=j; if((j<<1)<=n&&f[j<<1]+(v[j<<1][1]?-1:1)<f[j]) f[j]=f[j<<1]+(v[j<<1][1]?-1:1),g[j]=g[j<<1]; if((j<<1|1)<=n&&f[j<<1|1]+(v[j<<1|1][1]?-1:1)<f[j]) f[j]=f[j<<1|1]+(v[j<<1|1][1]?-1:1),g[j]=g[j<<1|1]; } for(j=pos;j;j>>=1) { f[j]=1<<30; if(c[j]&&0<f[j]) f[j]=0,g[j]=j; if((j<<1)<=n&&f[j<<1]+(v[j<<1][1]?-1:1)<f[j]) f[j]=f[j<<1]+(v[j<<1][1]?-1:1),g[j]=g[j<<1]; if((j<<1|1)<=n&&f[j<<1|1]+(v[j<<1|1][1]?-1:1)<f[j]) f[j]=f[j<<1|1]+(v[j<<1|1][1]?-1:1),g[j]=g[j<<1|1]; } } return 0; }
【BZOJ4849】[Neerc2016]Mole Tunnels 模拟费用流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。