Meul

11eyes的...

ACM(1) Atcoder(14) BFS(1) codeforces(38) DFS(2) dp(3) ICPC(1) sublime text 3(1) 容斥(1) 未归档(10) 模拟(1) 洛谷(2) 牛客(26) 牛客题霸(1) 题解(75)

/ 注册

全部文章 / 11eyes的算法笔记（共4篇）

P3523 [POI2011]DYN-Dynamite 来自专栏

Question 给一棵树,树上有一些关键节点，要求你选个点，使得关键节点到这些点中距离的最小值的最大值最小，求这个值。 Solution 显然这道题是可以二分的，二分的好处在于我们将原问题转化为了：对于一个树，选中最少的节点，使得任意关键节点到选中节点的最小距离，请问需要选中多少个节点？这样...

DFS 树上最小点覆盖二分树形DP DP BFS

2021-03-31

2 566

NC12606I 来自专栏

Solution 首先很容易看出这道题是一道换根DP。我们首先可以写一个DFS求出以某个节点为根的答案，一般根节点就取1号节点，是因为,一般1号节点是存在的，当然也可以随便取别的。重点是考虑答案的转移。假设已知节点的答案，我们需要哪些信息能够通过一定的方式转移到呢？将转移分为部分维护，左边部分为部...

换根DP 树形DP DP

2021-03-08

2 443

树的直径

之前写过一篇学军信友队趣味网络邀请赛 B.齐心抗疫，那篇文章中讲述了一种通过两次dfs就足以求得树的直径的方法，今天来学习另一种方法求树的直径——树形DP。定义树的直径：若树上两点u,vu,v间的最短路径最大，那么该路径的长度称为树的直径。（可以存在多条）区别两者的复杂度都是方法1：简洁方便...

树树的直径数据结构

2020-09-17

0 956

11eyes的算法笔记——Dijsktra算法(待更新链式前向星)

Dijsktra 适用条件：边权为正相关应用：求最短路，打印最短路路径初始化（如果求最短路求初始化所有节点为INF，所求的起点的为0）找出一个未被标记的、 d ...

2020-05-05

0 390