1.知识点
环形dp
环形 dp 的概念
• 环形dp与基环树在许多环形结构的问题中,我们可以在环中从某个位置把环断开,把这个环变成线性的,然后进行 \(dp\) 等操作。
• 把能通过上述操作解决的环形问题称作 "可拆解的环形问题" 。
环形 dp 的两种策略
• 第一次在任意位置把环断开成链,按照线性问题求解;第二次通过适当的条件和赋值,保证计算出的状态等价于把断开的位置强制相连。
• 把环断成链,然后复制一倍在末尾
基环树
• \(n\) 个点的树共有 \(n - 1\) 条边,如果再加上一条边,即 \(n\) 个点 \(n\) 条边,那树中必然会出现一个环。
• 把这种 \(n\) 个点 \(n\) 条边的联通无向图,即刚好包含一个环的图,称作 "基环树"。
• 如果不保证连通,那么 \(n\) 个点 \(n\) 条边的无向图也可能是若干棵基环树组成的森林,简称 "基环树森林"。
外向树
• \(n\) 个点 \(n\) 条边,每个点有且仅有 \(1\) 条入边的有向图,被称为 "外向树"。
• \(n\) 个点 \(n\) 条边,每个点有且仅有 \(1\) 条出边的有向图,被称为 "内向树"。
基环树的直径
• 基环树中最长的简单路径被称为基环树的最长链,其长度被称为基环树的直径。
基环树找环
• 自己一个很神奇的方法:
- 预处理出每个点的 \(father\)
- 从某个点开始,一直往它的 \(father\) 走,边走边做 \(vis\) 标记,当走到一个已经访问过的节点时,便找到了环。
Code:
int find(int u)//从 u 点开始找环
{
vis[u] = true;
node = u;
while (!vis[fa[node]])
{
node = fa[node];
vis[node] = true;
}
return node;
//node 为环的一点
}
T1
• \(n\) 个点,\(m\) 条边。每次从任意一个点出发,每次可以走向一个没有访问过的点,或者沿着第一次访问这个点时经过的边后退到上一个点。
• 每到达一个点时,把这个点的编号记录下来,这样最后会组成一个长度为 \(n\) 的序列,期望这个序列的字典序最小,求出这个序列。
• 对于 \(60\%\) 的数据,满足 \(n \leq 5000\), \(m = n - 1\)。
• 对于 \(40\%\) 的数据,满足 \(n \leq 5000\),\(m = n\)。
Solution
• 数据范围提示了做法 /kk。
• \(60 pts\) 就是白送的,容易可以发现一个性质:到达一个点时,一定要遍历完它的子树后才能返回。
• 题目要求字典序最小,于是用 \(vector\) 存图,对每个点的子树内进行排序,最后直接 \(dfs\) 即可。
• 而对于另外的 \(40 pts\),因为 \(m = n\),所以这是一棵基环树。
• 手玩一下基环树的样例可以发现,一定有一条边是无法经过的,我们枚举这条边,然后 \(dfs\) 即可。
• ps:加强版无法通过,可能是 \(vector\) 常数太大了/bx/bx。