做推广什么网站好,python做h5网站,郴州房产网,网站分成推广怎么做正题
题目链接:https://www.luogu.com.cn/problem/P6122 题目大意
给出nnn个点的一棵满二叉树#xff0c;每个点有容量cic_ici#xff0c;mmm次从pip_ipi处加一只仓鼠然后求每只仓鼠都到一个点的最短路径长度和。 1≤n≤1051\leq n\leq 10^51≤n≤105 解题思路
模拟费…正题
题目链接:https://www.luogu.com.cn/problem/P6122 题目大意
给出nnn个点的一棵满二叉树每个点有容量cic_icimmm次从pip_ipi处加一只仓鼠然后求每只仓鼠都到一个点的最短路径长度和。
1≤n≤1051\leq n\leq 10^51≤n≤105 解题思路
模拟费用流的思想就是…模拟费用流字面意思
因为是满二叉树我们对于每个节点维护一个往下最短的路径还有容量的节点需要注意的是路径上如果流量是反向的话长度要是−1-1−1。
然后暴力更新这条路径上的流量再更新一下刚刚那个东西就好了。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N4e510;
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*21](flow[x*21]0?-1:1)dis[x])dis[x]dis[x*21](flow[x*21]0?-1:1),pos[x]pos[x*21];return;
}
int main()
{scanf(%d%d,n,m);memset(dis,0x3f,sizeof(dis));for(int i1;in;i)scanf(%d,c[i]);for(int in;i1;i--)updata(i);for(int i1;im;i){int p;scanf(%d,p);int x0,cost2147483647/3,now0;for(int yp;y!0;y1){if(nowdis[y]cost)costnowdis[y],xy;now(flow[y]0?-1:1);}anscost;for(int yp;y!x;y1)flow[y];for(int ypos[x];y!x;y1)flow[y]--;c[pos[x]]--;for(int ypos[x];y!x;y1)updata(y);for(int yp;y!0;y1)updata(y);printf(%d ,ans);}return 0;
}
