A – 家族
这道题真的是送分题(快要想出来直接暴力枚举+并查集的时候去看了题解,最后发现就是这么 sb)。
考虑枚举频段区间\([L, R]\)(将边进行排序,确定下界之后再枚举上界),这个地方是\(O(m^2)\)的。每次枚举下界的时候都要初始化并查集,然后合并两个集合的时候按照大小来修改答案就行了。
这道题真的是送分题(快要想出来直接暴力枚举+并查集的时候去看了题解,最后发现就是这么 sb)。
考虑枚举频段区间\([L, R]\)(将边进行排序,确定下界之后再枚举上界),这个地方是\(O(m^2)\)的。每次枚举下界的时候都要初始化并查集,然后合并两个集合的时候按照大小来修改答案就行了。
在有向图中,有唯一的源地(入度为 0)和汇点(出度为 0),每一条边都有非负的容量,且整张图都会保证平衡状态。这样的图叫做网络流图。
每秒钟每条管道流动的液体最多。常用的算法是 Dinic。先做一次 BFS 划分层次,再用 DFS 来进行流动。Dinic 算法就是在网络图上对残存网络进行利用求得最大流。
其中值得一提的是,Dinic 算法中有一个优化方式可以快速求最大流——当前弧优化。当前弧优化可以在每次找残余网络之前记录遍历到的 head 指针,避免不必要的遍历。
这道题我在考场上打了一个错解,还骗到了 30 分。
正常的思路是:在最短路图上找到几个边进行修改。然而,最优的解决方案并不一定出现在最短路图上的边上,也可以通过修改次优边进行解决。所以,这道题其实跟最短路没什么太大关系,即使后面会用到 Djisktra 来求最短路。
我们可以把一个\(G(V, E), |V| = n, |E| = m\)复制\(n\)份,然后对于第\(k\)份图中的有向边\((u_k, v_k, w_k)\),可以生成一个副本来连接下一层的目标点,也就是每一条边会派生出\((u_k, v_{k + 1}, 0)\),当最后求最短路时,经过这样的一条边可以被认为是修改一条边,且,这个边是单向向下的,所以不会出现同一层修改多次的情况。最后只需要求这张图的最短路,然后判定满足\(dist[n_k] \leq c\)的最小\(k\)就行了。
这道题是 Kruskal 重构树的裸题。我们先来考虑从\(s\)出发的人形状态,我们要找到一个点点权小于\(L\)的点,就相当于在 Kruskal 重构树上倍增找到最后一个小于\(L\)的点。我们把符合人形规律的 Krukskal 树记为 Tl,其中构造它的方式就是把原来图上所有边的边权赋值为端点的最大值,然后按最小生成树的方式去构造重构树;符合狼形规律的 Kruskal 重构树被记为 Tu,其中构造它的方式就是将端点编号最小值赋为边权,然后按最大生成树的方式构造。之后,我们再到主席树中求交集即可,如果有交集那么查询结果为一个不为零的数,输出\(1\)即可;没有交集那么查询结果即为\(0\),输出\(0\)。
Kruskal 重构树是图的一种生成树,主要解决一类路径边权限制问题。Kruskal 重构树有按深度单调的性质,所以很容易就可以解决边权的取值限制。
Kruskal 重构树的建造方法和 Kruskal 算法建最小生成树的方法非常类似,但是结构有所不同:Kruskal 重构树将边权变成点权,点权依深度变小。我们假设有一张这样的图:
结论 节点个数为\(n\)的无根标号树的个数为\(n^{n-2}\)。
这个结论在很多计数类题目中出现,要证明它首先需要了解 Prufer 序列的相关内容。接下来给出证明。