P6122-[NEERC2016]Mole Tunnels【模拟费用流】

正题

题目链接:https://www.luogu.com.cn/problem/P6122

---

题目大意

给出(n)个点的一棵满二叉树，每个点有容量(c_i)，(m)次从(p_i)处加一只仓鼠然后求每只仓鼠都到一个点的最短路径长度和。

(1leq nleq 10^5)

---

解题思路

模拟费用流的思想就是....模拟费用流（字面意思

因为是满二叉树，我们对于每个节点维护一个往下最短的路径还有容量的节点（需要注意的是路径上如果流量是反向的话长度要是(-1)）。

然后暴力更新这条路径上的流量，再更新一下刚刚那个东西就好了。

时间复杂度(O(nlog n))

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=4e5+10;
int n,m,c[N],dis[N],pos[N],flow[N],ans;
void updata(int x){
	dis[x]=2147483647/3;pos[x]=0;
	if(c[x])dis[x]=0,pos[x]=x;
	if(dis[x*2]+(flow[x*2]>0?-1:1)<dis[x])
		dis[x]=dis[x*2]+(flow[x*2]>0?-1:1),pos[x]=pos[x*2];
	if(dis[x*2+1]+(flow[x*2+1]>0?-1:1)<dis[x])
		dis[x]=dis[x*2+1]+(flow[x*2+1]>0?-1:1),pos[x]=pos[x*2+1];
	return;
}
int main()
{
	scanf("%d%d",&n,&m);
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=n;i++)scanf("%d",&c[i]);
	for(int i=n;i>=1;i--)updata(i);
	for(int i=1;i<=m;i++){
		int p;scanf("%d",&p);
		int x=0,cost=2147483647/3,now=0;
		for(int y=p;y!=0;y>>=1){
			if(now+dis[y]<cost)
				cost=now+dis[y],x=y;
			now+=(flow[y]<0?-1:1);
		}
		ans+=cost;
		for(int y=p;y!=x;y>>=1)flow[y]++;
		for(int y=pos[x];y!=x;y>>=1)flow[y]--;
		c[pos[x]]--;
		for(int y=pos[x];y!=x;y>>=1)updata(y);
		for(int y=p;y!=0;y>>=1)updata(y);
		printf("%d ",ans);
	}
	return 0;
}