BZOJ4849[Neerc2016]Mole Tunnels——模拟费用流+树形DP

分手后的思念是犯贱 2022-01-13 04:01 200阅读 0赞

## 题目描述 ##

鼹鼠们在底下开凿了n个洞，由n-1条隧道连接，对于任意的i>1，第i个洞都会和第i/2（取下整）个洞间有一条隧

道，第i个洞内还有ci个食物能供最多ci只鼹鼠吃。一共有m只鼹鼠，第i只鼹鼠住在第pi个洞内，一天早晨，前k只

鼹鼠醒来了，而后n-k只鼹鼠均在睡觉，前k只鼹鼠就开始觅食，最终他们都会到达某一个洞，使得所有洞的ci均大

于等于该洞内醒着的鼹鼠个数，而且要求鼹鼠行动路径总长度最小。现对于所有的1<=k<=m，输出最小的鼹鼠行动

路径的总长度，保证一定存在某种合法方案。

## 输入 ##

第一行两个数n,m（1<=n,m<=100000)，表示有n个洞，m只鼹鼠。

第二行n个整数ci表示第i个洞的食物数。

第三行m个整数pi表示第i只鼹鼠所在洞pi。

## 输出 ##

输出一行m个整数，第i个整数表示当k=i时最小的鼹鼠行动路径总长度。

## 样例输入 ##

5 4  
0 0 4 1 1  
2 4 5 2

## 样例输出 ##

1 1 2 4

首先考虑建出费用流模型：源点向每个点连边，容量为初始在这个点的鼹鼠数，费用为$0$；每个点向汇点连边，容量为$c\_\{i\}$，费用为$0$，原图有通道的点之间互相连边，容量为$INF$，费用为$1$。每次从给定点(即将源点到一个点的容量$+1$)出发找到一条最短路并将路径上的边建出容量为$1$，费用为$-1$的反向边。这样做显然会$TLE$，我们考虑这个图的特殊性质：根据题意这是个完全二叉树。所以我们可以先树形$DP$求出每个点$i$子树中到它距离最短的点$f\[i\]$及这个点的编号$g\[i\]$。因为这是完全二叉树，保证树高是$log\_\{n\}$，所以可以暴力从给定点往上爬来找最短路的折点(即最短路起点和终点的$lca$)，然后修改路径上的边权并更新$f$与$g$。即模拟费用流找最短路和建反向边的过程。

#include<set>
    #include<map>
    #include<queue>
    #include<cmath>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<bitset>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int f[100010];
    int g[100010];
    int v[100010][2];
    int ans;
    int n,m;
    int x,mn;
    int c[100010];
    int main()
    {
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d",&c[i]);
    	}
    	memset(f,0x3f,sizeof(f));
    	for(int 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(int j=1;j<=m;j++)
    	{
    		scanf("%d",&x);
    		int pos,anc,sum=0;
    		mn=1<<30;
    		for(int i=x;i;i>>=1)
    		{
    			if(mn>f[i]+sum)
    			{
    				mn=f[i]+sum,pos=g[i],anc=i;
    			}
    			sum+=v[i][0]>=0?1:-1;
    		}
    		ans+=mn;
    		c[pos]--;
    		printf("%d",ans);
    		if(j!=m)printf(" ");
    		for(int i=x;i!=anc;i>>=1)
    		{
    			v[i][0]<0?v[i][0]++:v[i][1]--;
    		}
    		for(int i=pos;i!=anc;i>>=1)
    		{
    			v[i][1]<0?v[i][1]++:v[i][0]--;
    		}
    		for(int i=x;i!=anc;i>>=1)
    		{
    			f[i]=1<<30;
    			if(c[i]&&f[i]>0)
    			{
    				f[i]=0,g[i]=i;
    			}
    			if((i<<1)<=n&&f[i<<1]+(v[i<<1][1]>=0?1:-1)<f[i])
    			{
    				f[i]=f[i<<1]+(v[i<<1][1]>=0?1:-1),g[i]=g[i<<1];
    			}
    			if((i<<1|1)<=n&&f[i<<1|1]+(v[i<<1|1][1]>=0?1:-1)<f[i])
    			{
    				f[i]=f[i<<1|1]+(v[i<<1|1][1]>=0?1:-1),g[i]=g[i<<1|1];
    			}
    		}
    		for(int i=pos;i;i>>=1)
    		{
    			f[i]=1<<30;
    			if(c[i]&&f[i]>0)
    			{
    				f[i]=0,g[i]=i;
    			}
    			if((i<<1)<=n&&f[i<<1]+(v[i<<1][1]>=0?1:-1)<f[i])
    			{
    				f[i]=f[i<<1]+(v[i<<1][1]>=0?1:-1),g[i]=g[i<<1];
    			}
    			if((i<<1|1)<=n&&f[i<<1|1]+(v[i<<1|1][1]>=0?1:-1)<f[i])
    			{
    				f[i]=f[i<<1|1]+(v[i<<1|1][1]>=0?1:-1),g[i]=g[i<<1|1];
    			}
    		}
    	}
    }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10428986.html