「BZOJ1808」「IOI2007」训练路径-DP

发布于 19 天前  53 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「BZOJ1808」「IOI2007」训练路径-DP

Description

给定一张图与该图的一张生成树,每个点度数不超过10。
其中可以删去非生成树上的边。每条边有一个权值,求代价最小的删边方案使得图中不存在偶环。

Solution

显然可以删去在两点树上路径长度为奇数的边。

之后可以发现图中存在存在偶环的充分必要条件为存在一个环经过了两条非树边(因为两个有公共边的奇环删去公共边后得到了一个偶环)

把答案转化用总权值前去可以留在图中的最大权值,所以题目转化为一个图的最大生成仙人掌。

这时候发现一个点的度数不超过\(10\),所以我们可以在生成树上状压DP。

设\(f_{i,s}\)表示以\(i\)为根的子树,不考虑\(s\)集合中的儿子的最大权值。

转移看这张图吧,讲的很清楚。

转移

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「BZOJ1808」「IOI2007」训练路径-DP


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前,相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!