求树的最大独立集,最小点覆盖,最小支配集 贪心and树形dp
(有任何问题欢迎留言或私聊&&欢迎交流讨论哦
求树的最大独立集,最小点覆盖,最小支配集
三个定义
最大独立集:
对一个图选出尽量多的点组成一个集合,满足这些点之间没有边相连。所有独立集中,顶点数最多的称作最大独立集。
最小点覆盖:
对一个图选出尽量少的点组成一个集合,满足图中所有的边均有端点属于这个集合。所有覆盖集中,顶点数最少的称作最小点覆盖。
最小支配集:
对一个图选出尽量少的点组成一个集合,满足图中剩余的点都和集合中的点有边相连。从集合中出去任何一个点之后若不再是支配集,则此支配集是极小支配集。所有支配集中,顶点数最少的称作最小支配集。
贪心解法
树的最大独立集:
先求一遍dfs序,倒序遍历。若此节点未被标记,则将此端点加入独立集,并标记此节点和其父节点。
树的最小点覆盖:
先求一遍dfs序,倒序遍历。若此节点及其父节点均未被标记,则将其父节点加入覆盖集,并标记此节点及其父节点。
树的最小支配集:
先求一遍dfs序,倒序遍历。若此节点未被标记,把其父节点加入支配集(前提是它不在支配集中),然后标记此节点,父节点及其爷爷节点。
树形DP解法
树的最大独立集:
\(dp[i][0]\)表示点i在独立集中;\(dp[i][1]\)表示点i不在独立集中
\[
dp[u][0] = 1 + \sum dp[v][1];\\
dp[u][1] = \sum max(dp[v][0], dp[v][1]);
\]
树的最小点覆盖:
\(dp[i][0]\)表示点i在点覆盖集中;\(dp[i][1]\)表示点i不在点覆盖集中
\[
dp[u][0] = 1 + \sum min(dp[v][0], dp[v][1]);\\
dp[u][1] = \sum dp[v][0];
\]
树的最小支配集:
\(dp[i][0]\)表示点i属于支配集,并且以点i为根的子树都被覆盖了的情况下支配集中所包含最少点的个数
\(dp[i][1]\)表示点i不属于支配集合,且以i为根的子树都被覆盖,且i被其中不少于一个子节点覆盖的情况下支配集所包含最少点的个数
\(dp[i][2]\)表示点i不属于支配集合,且以i为根的子树都被覆盖,且i没被子节点覆盖的情况下支配集中所包含最少点的个数.即i将被父节点覆盖
\[
dp[u][0] = 1 + \sum min(dp[v][0],dp[v][1],dp[v][2]);\\
dp[u][2] = \sum dp[v][1];dp[u][2]=min(dp[u][2],INF);\\
if(dp[v][0]<=dp[v][1]) inc = 0;(if\;0\;always\;0)\\
else\;inc = min(inc, dp[v][0]-dp[v][1]);\\
if(u\;no\;son)dp[u][1] = INF;\\
else\; dp[u][1] = \sum min(dp[v][0],dp[v][1])+inc;
\]
参考博文:Ash-ly
最新文章
- WebAPI2使用AutoFac依赖注入完整解决方案。
- 使用样式“clear”和“overflow”消除浮动元素对环绕行框的影响
- Codeforces 13C Sequence --DP+离散化
- Bootstrap 下拉菜单和滚动监听插件
- 开发与测试整体过程中的Git分支merge流程
- Linux安装IDA神器
- 用Grunt搭建基于LESS的前端html开发框架
- 利用 __FUNCTION__ 宏打印函数调用信息
- shell/bash 让vi/vim显示空格,及tab字符
- 黑马程序员 c#单态的设计模式 (专题二)
- java星座、年龄、日期等
- jquery height、innerHeight、outHeight
- ecostore搜索注意事项
- git分支管理之Feature分支
- 纯Css绘制三角形箭头三种方法
- NOIP-Vigen&#232;re密码
- Java开发笔记(十四)几种运算符的优先级顺序
- 20165221-week2课上测试补做
- Webpack+Typescript 简易配置
- E - Coin Game