首页 > 编程语言 >较快速的最大带权独立集算法

较快速的最大带权独立集算法

时间:2024-09-25 21:15:00浏览次数:6  
标签:frac text 独立 long 算法 带权 快速 dp

前言

重新来吧 别输在过去最得意的事上。

只是单纯的记录一下这个小知识点。

很多时候,题目可以转化为求最大带权最小点覆盖或者是最大独立集。

但是他又经常把这个范围给到 \(n\le 40\) 这种看上去可以用指数又不太能用指数的情况。

可能这个时候你就需要用到短小精悍的它。

基于状压和折半的独立集算法

首先给出我开始弄明白这个小知识点的来源题目:CF1767E Algebra Flash

题意是比较清楚的。

而你要从起点到达终点的一个充分必要条件是:

  • 必须选择起点和终点。

  • 相邻两个点必须选择一个点。

故你考虑对于起点和终点的颜色连一个自环,然后将相邻两个点分别对应的颜色连一条边。

故这个题就转化成了一个一般图最小带权点覆盖的问题。

而我们知道最小带权点覆盖 \(=\) 点权和 \(-\) 最大带权独立集。(注意这个东西在一般图上也是存在的

故我们只需要知道这个图的最大带权独立集是什么。

首先有一个很 \(\texttt{naive}\) 的状压是定义 \(dp_S\) 表示只选择 \(S\) 内部的点可以构成的最大独立集是多少。

另外,我们定义点 \(x\) 的邻域的点构成的集合是 \(N(x)\)。

转移的话本质上我们只需要考虑这个集合中的任意一个点就行了,为了方便我们后面的优化,考虑 \(\text{highbit}(S)\),假设是 \(u\)。

显然有:\(dp_S=\max(dp_{S-u},dp_{S-N(u)-u}+w_u(u\not \in N(u)))\)。(显然如果是自环的话你不能把这个点当作最大独立集上的点)

时间复杂度 \(\mathcal{O}(2^n)\)。

但是这里 \(n\le 40\) 显然不可过啊。

于是我们考虑一个奇技淫巧,也是这个算法的关键所在。

首先先把这个 \(\text{dp}\) 搬到记忆化搜索上面。由于我们使用的是 \(\text{highbit}(S)\),故这个 \(S\) 在搜素过程中逐渐减小。故我们考虑只对 \(s < 2^{\frac{n}{2}}\) 这部分进行记忆化,而剩下的部分直接爆搜,具体见下:

long long dfs(long long sta)
{
    if(sta <= lim && ~dp[sta]) return dp[sta];
    if(sta == 0) return 0;
    int x = __lg(sta);
    long long ans = dfs(sta - (1ll << x));
    if(!((1ll << x) & d[x + 1])) ans = max(ans, dfs(sta - (1ll << x) - (sta & d[x + 1])) + w[x + 1]);
    if(sta <= lim) return dp[sta] = ans;
    return ans;
}

时间复杂度我们简单的证明一下。

对于搜索的前 \(\frac{n}{2}\) 层,每向下递归一次,最多只会变成两个,故前半是 \(\mathcal{O}(2^{\frac{n}{2}})\)。

对于后面的 \(\frac{n}{2}\) 层,显然都会被记忆化到,无论你前面有多少种状态,加起来仍然只有 \(2^{\frac{n}{2}}\) 级别。(就是在记忆化和非记忆化分层的哪些点只有 \(2^{\frac{n}{2}}\) 而他们分别向外扩展也只会扩展成 \(2^{\frac{n}{2}}\) 级别,有点像 \(\text{Meet in the middle}\) 那种感觉)

故总时间复杂度 \(\mathcal{O}(2^{\frac{n}{2}})\)。

本题代码和更多细节见

后记

还有一个叫做 \(\text{Bron-Kerbosch}\) 的算法,笔者认为在 \(\texttt{OI}\) 中的实用性远不如文章中这一种,故略过。

参考资料:《浅谈信息学竞赛中的独立集问题》 - 学习笔记

缝缝补补,缺漏的知识点会补的完吗?

标签:frac,text,独立,long,算法,带权,快速,dp
From: https://www.cnblogs.com/SFsaltyfish/p/18432219

相关文章

  • idea怎么快速生成get set方法,快捷键是什么?
    idea怎么快速生成getset方法参考文章:IntelliJIDEA生成get/set方法的快捷键是什么1、生成某个getset方法alt+enter快捷键:alt+enter2.生成整个类或者某个getset方法alt+insert快捷键:alt+insert点击后,会出现下图弹窗,你可以多选或者单选这些属性对象,然后点击ok......
  • 信息安全工程师(18)常见密码算法
    前言  常见的密码算法主要分为三大类:对称加密算法、非对称加密算法和摘要算法。一、对称加密算法    对称加密算法,又称为秘密密钥算法或单密钥算法,是指加密和解密使用相同密钥的加密方式。这种算法的特点是加密速度快,适用于大量数据的加密。常见算法:AES(Ad......
  • SqlEs快速入门
    可以参考demo:https://github.com/czcuestc/sqles/tree/master/sqles-demo1,使用SqlEs很简单,首先创建实体类,通过注解配置索引,示例如下:@Document@Setting(maxResultWindow=1000)publicclassTestEntityimplementsSerializable{privatestaticfinallongserialVers......
  • 快速部署MySQL数据库
    一.下载对应的软件版本下载地址:http://mirrors.sohu.com/mysql/MySQL-5.6/备用地址:http://ftp.ntu.edu.tw/pub/MySQL/Downloads/[root@localhost~]#wget-qhttp://mirrors.sohu.com/mysql/MySQL-5.6/sql-5.6.36-linux-glibc2.5-x86_64.tar.gz二、解压、配置用户和权限[root@loca......
  • 编码探索:卡布列克常数的算法之旅
    数字的魔法:给我任意一个四位数,通过排列和减法,最终总能得到6174——卡布列克常数。本文用代码演示了这一神奇过程,带你领略数学的奇妙和编程的乐趣。卡布列克常数(Kablekconstant):任意一个不是由完全相同数字组成的四位数,如果对它们的每位数字重新排序,组成一个较大的数和一个较小的......
  • WPS演示 wpp.exe系统错误ntdll丢失怎么办?WPS演示wpp.exe ntdll.dll丢失快速恢复指南
    当WPS演示(wpp.exe)遇到系统错误提示“ntdll.dll丢失”时,这通常意味着Windows操作系统中的一个关键动态链接库文件(DLL)丢失或损坏,导致WPS演示无法正常运行。以下是一个快速恢复指南,帮助您解决这一问题:一、重新启动计算机首先,尝试最简单的解决方案——重新启动计算机。有时,简单......
  • 《守望先锋2》libcef.dll文件丢失无法运行?快速定位并解决《守望先锋2》libcef.dll文件
    《守望先锋2》在运行时提示libcef.dll文件丢失,这确实是一个可能导致游戏无法正常运行的问题。以下是一些快速定位并解决这一问题的步骤:一、了解libcef.dll文件libcef.dll文件通常与ChromiumEmbeddedFramework(CEF)相关,它对于游戏内嵌的网页内容展示与交互至关重要,如登录界面......
  • IP地址解析(算法题)
    例题讲解:例题1:IP地址解析(拼多多面试题)给定一个字符串表示的IP地址,如“123.92.2.34”,判断其是否合法。合法IP地址的规则如下:a.除了空格、数字和.之外,不得包含其他字符。b.IP地址由四个数字构成,由.分隔,每个,隔开的数字大小在0~255之间。c.数字前后可以有空格,但中间不能......
  • word怎么删除空白页?3个方法,快速排版
    盆友们!你是不是经常在Word文档中遇到那些让人头大的空白页呢?它们就像隐形的障碍物,让你的排版工作变得复杂又繁琐。word怎么删除空白页?别担心,今天我就来给大家分享3个快速有效的方法,帮你轻松删除这些烦人的空白页,让你的Word文档瞬间变得井井有条。方法1:Backspace键——直截......
  • 滑动窗口算法以及应用
    滑动窗口算法以及应用主要涉及以下几个关键参数和概念:窗口大小(WindowSize):这是滑动窗口的宽度,决定了窗口中包含的数据点数量。例如,如果你在处理时间序列数据,窗口大小可能定义为秒、分钟或小时的数量。窗口位置(WindowPosition):由左右边界(通常是两个指针)定义的窗口在数据序列......