PKU2019数据结构与算法实习模板

2019年12月29日9730

本文包括:

并查集 最短路 强连通分量 线段树 AC自动机(Trie) 网络流 后缀数组

POJ1182 食物链

如果并查集中 X 向 Y 连边长为 1 的边,代表 X 吃 Y

这题如果用按秩合并并查集比较好想,带路径压缩的话,需要考虑重新连边的时候,边权的设置

POJ1860 Currency Exchange

最短路模板

POJ2186 Popular Cows

如果 X 喜欢 Y,Y 向 X 连边。缩点以后,计算每个强连通块的入度,唯一的入度为 0 的块大小就是答案。

POJ2528 Mayor’s posters

离散化后用线段树实现区间染色,最后 dfs 一遍

多模式串字符串匹配模板题 http://dapractise.openjudge.cn/2019hwall/010/

AC自动机

POJ2112 Optimal Milking

网络流模板

POJ3450 Corporate Identity

这个后缀数组模板是从课程 ppt 上拷贝下来的

avatar
  Subscribe  
提醒