正題

題目鏈接:https://www.luogu.com.cn/problem/P6122

---

題目大意

給出$n$個點的一棵滿二叉樹，每個點有容量$c_i$，$m$次從$p_i$處加一只倉鼠然后求每只倉鼠都到一個點的最短路徑長度和。

$1\le n\le 10^5$

---

解題思路

模擬費用流的思想就是…模擬費用流（字面意思

因為是滿二叉樹，我們對于每個節點維護一個往下最短的路徑還有容量的節點（需要注意的是路徑上如果流量是反向的話長度要是$?1$）。

然后暴力更新這條路徑上的流量，再更新一下剛剛那個東西就好了。

時間復雜度$O(n\log 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; }

總結

以上是生活随笔為你收集整理的P6122-[NEERC2016]Mole Tunnels【模拟费用流】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。