hdu6403问题中如何结合基环树和DFS进行动态规划求解？

本文共计1836个文字，预计阅读时间需要8分钟。

首先图得出来才有后话（反向思维是建不出来+图是这样建的）。从背面数字向正面数字连线，题目转化成反向最少边的深度不大于1。然后要讨论一下。

首先图得建得出来才有后话（反正窝是建不出来

图是这样建的。。从反面数字向正面数字连边，然后题目转化成反向最少的边使所有点的入度不大于1

然后就要讨论一下了。。根据容斥原理，对一个连通块如果边数大于点数那么必定有点是入度大于1的。。所以每个连通块只能是树或者基环树。。

树的话可以根据容斥原理得到有一个点的入度是0的，所以可以枚举这个入度为0的点，转成有根数，根据有根树的方向将边反向即可。。实现的时候先算一个点然后用这个点的反转边数来推到另一个边的反转边数，可以说是DP吧。。。2遍dfs就求出来了。。

然后对基环树的情况，首先外向树的边已经定向，一遍dfs找出反转边数。。然后讨论一下环上顺时针和逆时针的反转情况，取最小或者都取。。

就是分类讨论写起来烦了一点。。难度其实不大。。

然后被无向图2点环坑了好久。。以后写基环树的时候一两点的情况得考虑清楚。。