题目链接

题目链接
本题是2005年ACM ICPC 欧洲区域赛 西北 赛区的 E 题 。
题意
参见CSDN博主「」的原创文章,这里贴一下他写的题意:
有一个有n个关键点的洞窟的路线图,其中1为入口 。
保证只有一个点与1相连,且每个点最多只跟三个点有连边,以及从每个点到1的路有且仅有一条 。
洞窟中还有m个陷阱,位于m个关键点中 。
英雄从入口走到了某个死胡同且一路上没有触发到任何陷阱,之后英雄在这个死胡同里安营扎寨 。
我们的目的是协同恶法师将英雄找出来,为此需要找遍所有的【从入口到终点一路上没有陷阱】的死胡同 。
但是我们所在的宫殿离洞窟太远了,并没有办法从入口进去,所以只能通过传送门派小兵过去找 。
恶法师可以从某条道路上开启一个传送门,并将小兵们从远方的宫殿送往这条路上 。

题目链接

文章插图
小兵一开始的行动方向为背离入口的方向,每次遇到一个岔路口必定选择左边的路走,遇到死胡同就掉头 。
你可以令小兵在遇到某个岔路口时选择右边的路而不是左边的路,不同的小兵可以选择不同的岔口但是每只小兵最多只能右转一次 。
当小兵走回传送门的时候就会被传送回去 。
小兵遇到陷阱会死掉,所以你必须令小兵避开陷阱 。
问找遍所有符合条件的死胡同所需要开的最少的传送门数 。
还有一点是通过枚举题意推出来的:小兵所走过的路中不能有出来送小兵来的传送门之外的其他传送门
以及还有一点需要注意的是,对于小兵来说的左边并不是我们看地图的视角的左边,而是小兵自己在洞窟里的视角的左边 。
博主「」的这个题意分析基本能懂,但“对于小兵来说的左边并不是我们看地图的视角的左边,而是小兵自己在洞窟里的视角的左边”这句还是有点懵,我又从原创力文档上找到了雅礼中学女神大佬陈丹琦的题解:
两相结合,这一点我就理解了,这里我再补上一张图方便读者理解:
题目链接

文章插图
从父节点前进视角,若左转将走向左子节点,若右转将走向右子节点;
从左子节点回退视角,若左转将走向右子节点,若右转将走向父节点;
从右子节点回退视角,若左转将走向父节点,若右转将走向左子节点 。
【题目链接】分析
理解完题意后,就知道用树上的动态规划求解了 。
博主「」的动态规划使用的状态是d[N][3]:d[i][0]表示节点u的父节点和i的道路上无兵通过时,访问找遍子树i所有符合条件的死胡同所需要开的最少的传送门数;d[i][1/2]表示节点i的父节点和u的道路上有兵通过(但没有右转过/已经右转过),访问找遍子树i所有符合条件的死胡同所需要开的最少的传送门数 。这样的状态转移需要分类讨论,不一一细述 。
陈丹琦的动态规划状态是:用trap[i]表示子树i是否有陷阱(节点i本身是陷阱或者i的子树有陷阱则子树i有陷阱),f[i]表示访问完i这个子树最少需要安排多少传送门,g[i]表示已经为节点i和其父节点的道路上安排了传送门,遍历完整个子树i另外最少还需要多少个传送门 。女神大佬的这个动态规划状态转移就简洁很多了:f[i] = min(f[] + f[], 1+g[i]) 。若trap[] && trap[],则g[i] = +inf;否则g[i] = min(g[] + g[], g[] + f[], g[] + f[]) 。
AC代码
博主「」的动态规划:
#include using namespace std;#define N 50010#define M 505int d[N][3], g[N][3], c[N], n, m; bool trap[N];void dfs(int u, int fa = 0) {if (trap[u]) {d[u][0] = 0; d[u][1] = d[u][2] = N;} else if (c[u] == 1 && u > 1) {d[u][0] = 1; d[u][1] = d[u][2] = 0;} else if (c[u] == 2 || u == 1) {int s = u==1 ? g[u][0] : g[u][0]+g[u][1]-fa;dfs(s, u);d[u][0] = d[s][0]; d[u][1] = d[s][1]; d[u][2] = d[s][2];} else {int l = g[u][0]!=fa ? g[u][0] : g[u][1], r = g[u][0]+g[u][1]+g[u][2]-fa-l;dfs(l, u); dfs(r, u);d[u][2] = d[l][2] + d[r][2];d[u][1] = min(d[l][2] + min(d[r][0], d[r][1]), d[r][2] + min(d[l][0], d[l][1]));d[u][0] = min(d[l][0] + d[r][0], 1 + d[u][1]);}}int solve() {for (int u=1; u