Meul

题解

11eyes的算法笔记(4) ACM(1) Atcoder(14) BFS(1) codeforces(38) DFS(2) dp(3) ICPC(1) sublime text 3(1) 容斥(1) 未归档(10) 模拟(1) 洛谷(2) 牛客(26) 牛客题霸(1)

/ 注册

全部文章 / 题解（共5篇）

NC9985A美丽的路径来自专栏

Question 给定点权无向图，求任意由到的路径中最大的第小的点权。 Solution 二分答案，假设答案为，则对于第小的点权，我们将其转化为该路径上有的点，他们的点权值。我们将路径上的点染色分为两种点：，染为。，染为。有如下情况：一. 与不联通，二. 与联通，路径上存在两个连续...

DFS 二分

2021-02-23

4 623

NC20568 [SCOI2012]滑雪与时间胶囊

Question 有1到n个景点，每个景点有一个高度h，从1号节点出发，求能到达多少个景点和最小生成树。 Solution 预处理有向边建图 Kruscal这道题和普通的求最小生成问题的区别在于，这里是有向路，高度只能从高到低(可以相等)。那我们需要从1号节点开始dfs预处理能够走得通的有向路，并将...

kruscal dfs

2020-05-01

0 596

NC201400

题意一棵个结点的树，令根节点的深度,其他节点的深度为，求以某个点为根节点这棵树的最小为多少？思路我们要枚举每一个结点为根节点的为多少，我们可以先求得以某片叶子为根节点的，然后再找寻相连的的关系，记录最小值。以某一片叶子为根节点，DFS遍历整棵树，算其深度，算该节点的子树结点数量为。(无根树很多...

dfs 树

2020-04-16

0 667

NC14248

NC14248 题意给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同思路 DFS 树数据结构这道题和CF1339D十分相像，有兴趣的可以做一下。把题意转化为给你一颗n个结点的树，树上所有的边权值为1，求树...

DFS 树数据结构

2020-04-14

2 774

NC13886

NC13886 题意给你一颗n(偶数）结点的树，将其分为n/2对，求所有对数相连的路径之和最小为多少？思路 DFS 数据结构既然是图论那就先画图吧左图由于以2号结点为根节点的子树结点数(包括其自身)为3（奇数），那么显然这棵树上一定有个节点要从树外找一个节点相连，那么必须要经过2号结点与其父节点...

DFS 数据结构

2020-04-02

0 493