rprp

图论

动态规划(12) 字符串(3) 搜索(1) 数学(6) 数据结构(18) 未归档(2) 贪心(5) 配置(2)

/ 注册

全部文章 / 图论（共6篇）

图论学习（在更）

note: 最小环是枚举已有的最短路和k点连接的两条边，保证三个点不重合。 for(R int k = 1; k <= n; k ++) { for(R int i = 1; i < k; i ++) for(R i...

图论

2020-08-11

0 542

Luogu P3350 [ZJOI2016]旅行者

这题正常的题面请看这里由大佬之言可知，看见网格图想分治　　所以这题考虑分治。　　考虑把棋盘分成两半，那所有点就会有两种情况：在完整的一半以内跨越两半考虑在我们分成两半的那条中线的所有点跑最短路来更新所有点的答案。然后对于跨越了两半的点就直接保存答案，在同一块的点就类似整...

最短路分治

2020-05-06

0 402

Luogu P2056 [ZJOI2007]捉迷藏

动态点分治先建出一颗点分树，然后维护。对于每一个点维护两个堆，一个堆维护子树内所有点到分治父节点的距离最大值，一个堆维护一个点所有子树的第一个堆的最大值，再全局维护一个堆取所有分治重心的答案的最大值即可。代码细节感人。。。一个比较有用的trick就是用两个大根堆实现可删除的堆但是要开O2 ...

堆动态点分治

2020-05-04

0 396

Luogu P3292 [SCOI2016]幸运数字

看到异或最值，显然想到线性基。用树上倍增的方法，维护当前点\(x\)到倍增父节点\(fa[x][i]\)这条路径上的线性基，在倍增的时候暴力合并即可。注意这个线性基的倍增数组是没有包括最后一个点的信息的，需要特殊处理。然后就搞完了。时间复杂度\(O(n*log_n*log_v+q*log_n*...

倍增线性基

2020-05-03

0 373

Luogu CF555E 【Case of Computer Network】

其实如果这是一颗树的话很好搞，把\(s\)到\(lca(s,t)\) 向上连，\(lca(s,t)\)到\(t\)向下连即可(然而事情并不是这样子的...)。我们考虑什么样的情况是一定可行的呢？每两个点之间都有两条以上的路径，那就可以一边向前，一边向后，绝对可以。也就是求双联通分量以内是一定可以的...

边双联通分量

2020-05-02

0 424

Luogu P4151 [WC2011]最大XOR和路径

原题传送门看见异或最值，估计线性基跑不了了。考虑先随便提出一条从\(1\)到\(n\)的路径，这显然不一定是最优的，但是可以让它变强。比如可以让它中间插入一个环来让它变优。比如说有一条路径: \(1->A->B->C->N\) 可以补成： \(1->A->B-...

线性基妙啊

2020-05-02

0 407