wxwoo's blog

原题目链接

明显的最大权闭合子图

最大权闭合子图：

给定一个有向图，点有点权，选择一个子图，满足子图上如果选择了一个点就必须选择它后继的所有点。最大化点权和。

经典的网络流问题，具体使用最小割求解

我们将顾客和通讯站都看成一个点，然后如下建边：

1. 源点向顾客连流量为利润的边

2. 通讯站向汇点连流量为成本的边

3. 每个顾客向需要的通讯站连流量为inf的边

原题目链接

前置知识：不带修区间最大子段和

没做过请先右转GSS1

这题比GSS1多了一个对左右端点的区间限制，GSS1的做法不再适用

这时我们就要分两种情况讨论

原题目链接

树上链最值查询

做法很多，LCT，树上倍增，树剖都可以

但由于LCT常数过大，树上倍增比树剖常数大，这里使用树链剖分

边权转点权是树剖常用套路，将边权转成深度较大的点的点权，查询时注意避开两点的LCA的权值

由于不带修改，树剖后用ST表维护，时间复杂度$\mathcal{O}(n\log n)$，比用线段树维护$\mathcal{O}(n\log ^2n)$还少一个log

原题目链接

首先想到$\Theta(n^4)$的暴力枚举，但$n\le 4000$显然不行。

考虑先预处理出c数组和d数组的和，再暴力计算答案。

由于c数组和d数组的和可能会有重复，排序后使用二分来降低时间复杂度

最终时间复杂度$\Theta (n^2\log n)$

原题目链接

看到题目就想到了dfs+剪枝

然后就想到了dfs有问题

例如这组数据

1
2
3

4-9-12
| | |
2-4-10

从4开始，到10结束

dfs会走$4 \to 2 \to 4 \to 10$，答案为8

然而很明显走$4 \to 9 \to 4 \to 10$更优，答案为6

当然你加一大堆玄学优化也是可以搜出正确答案的

这里不再多讲，而是提供另一种思路：

二分