AvariceZhao

题解

/ 注册

全部文章 / 题解（共3篇）

洛谷 P3384 【模板】轻重链剖分/树链剖分

【模板】轻重链剖分/树链剖分题目描述如题，已知一棵包含 NNN 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作： 1 x y z，表示将树从 xxx 到 yyy 结点最短路径上所有节点的值都加上 zzz。 2 x y，表示求树从 xxx 到 yyy 结点最短路径上所有...

C++ 线段树

2022-10-03

0 348

题解 | #托米去购物#

题意有一些商品和一些优惠券，每张优惠券有一定金额并且可以拆分并可以用于某些商品，问最少要付多少钱思路比较经典的最大流建模，把“货物”看作水流，本题中的货物指优惠券的金额，每张优惠券的金额可以“流向”特定的商品，用水流代金额的流动，每张优惠券的可用金额是源点连向优惠券的容量，商品的价格是商品到汇...

C++ 图

2022-08-29

1 509

题解 | #Forsaken喜欢独一无二的树#

题意删除一些边，使得最小生成树唯一，问删除的边的权值和最小是多少？思路 kruskal按边权从小到大排序后可以视为将所有边按边权分段，在同一段内先将可能的边全部计入，随后遍历这一段长度相同的边，对于左右端点不在同一集合里的边将边权从累加的边权和删去，即保留一条最小生成树中的边。剩余的即为应删去的...

最小生成树

2022-07-09

0 349