2020-2021:teams:too_low:0808-0814
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:too_low:0808-0814 [2020/08/14 17:34] member [比赛] |
2020-2021:teams:too_low:0808-0814 [2020/08/14 17:52] (当前版本) member [陈源] |
||
|---|---|---|---|
| 行 65: | 行 65: | ||
| ==== 李英龙 ==== | ==== 李英龙 ==== | ||
| - | 无 | + | [[https://blog.csdn.net/dragonylee/article/details/107895708|ACM算法总结 prufer序列]] |
| ==== 陈源 ==== | ==== 陈源 ==== | ||
| - | 无 | + | CF1391E-Pairs of Pairs |
| + | |||
| + | **题意：**给定一个联通图，无重边无自环，保证以下两个条件只满足一个 | ||
| + | |||
| + | - 存在一条简单路径（路径上每个点只经过一次），这条简单路径覆盖了至少n/2向上取整个点 | ||
| + | - 可以从图中选出至少n/2向上取整个点，将其两两分组，任意两组点(A,B),(C,D)，原图中这四个点的诱导子图，至多有两条边。 | ||
| + | |||
| + | 如果满足第一个则输出路径上的点，满足第二个则输出分组。 | ||
| + | |||
| + | |||
| + | 这道题利用了图的dfs树，dfs树就是平时tarjan算法用的那个，之前基本都是当作黑盒算法来用的，dfs树可以用来解决一些和tarjan算法看起来关系不大的问题，也是解决仙人掌问题的利器。 | ||
| ==== 胡琎 ==== | ==== 胡琎 ==== | ||
2020-2021/teams/too_low/0808-0814.1597397683.txt.gz · 最后更改: 2020/08/14 17:34 由 member
