Z_L_G

分类

总结(9) 训练赛(6) 题解(68)

/ 注册

全部文章（共2篇）

最小支配集-最小点覆盖-最小边覆盖

最小点覆盖 (Minimum Vertex Cover, MVC) 用最少数量的顶点覆盖图中所有的边。最小边覆盖 (Minimum Edge Cover, MEC) 用最少数量的边覆盖图中所有的顶点。最小支配集 (Minimum Dominating Set, MDS) 用最少数量的顶...

最小点覆盖最小支配集最小边覆盖

2025-05-16

0 15

算法入门-(USACO 2008 Jan G)Cell Phone Network(最小支配集)

最小支配集选择一个点，可以覆盖相邻的点，覆盖所有点所需最小选点题意给定一颗n个结点的树，求最小支配集思路考虑每一个点，他可能被支配的方式有：被父亲支配，选自己，被儿子支配，维护一个二维dp数组记录点和状态：自己：父亲：儿子：对于自己和父亲，状态方程很显然可以推出，对于...

dp 树形dp 深度优先搜索最小支配集

2025-05-16

0 19