首页 > 其他分享 >一般图边覆盖计数(从洛谷博客同步)

一般图边覆盖计数(从洛谷博客同步)

时间:2024-06-10 10:43:53浏览次数:17  
标签:从洛谷 钦定 边覆盖 点集 计数 划分 枚举 做法 复杂度

今天模拟赛中出现了一个题,需要对一个 \(n\) 个点,\(m\) 条边的图做边覆盖计数,边覆盖是一个边集 \(S\subseteq E\) 使得任意一个点 \(i\) 都存在一条边 \((u,v)\in E\) 满足 \(u=i\) 或 \(v=i\),即覆盖所有的点。

\(n\leq 40,m\leq 60\),1s 512M。

然后被我使用神秘做法冲过去了(然后莫名其妙登顶?)求叉 & 求证明。

这是一个 NPC 问题。

做法1(题解)

考虑类似 meet-in-the-middle 地将图划分成两块 \(A,B\),分别求出 \(f(S),S\subseteq A\) 和 \(g(S),S\subseteq B\) 表示在 \(A,B\) 的导出子图内选择若干边,覆盖点集 \(S\) 的方案数,剩下需要考虑 \(A-B\) 之间的边,令其有 \(L\) 条,我们对 \(2^{|L|}\) 地枚举所有选中间的边的方案,则会要求两侧有一些点必须被覆盖,

该算法的时间复杂度是 \(O(2^{S}S+2^L)\),其中 \(S=\max(|A|,|B|)\),直接随机大量划分 \(A,B\) 的方案并计算该值,取复杂度最小的划分 \(A,B\) 来进行计算,题解瞎几把证明了一通并声称能过。

一个能将本做法卡至相对较高复杂度的数据是两个相对着的菊花,形如 \((1,3),(2,3),(1,4),(2,4)\dots (1,n),(2,n)\),这个时候最优的划分是将 \(1,2\) 划分至同一侧,剩下的点相对不平均地划分,要是平均地划分边会多达 \(30\) 条,随机到一侧点集稍大可以使得边数处于可以接受的范围内,最终复杂度较有时可能会达到大概 \(2^{26}\) 左右。

基于点的统计

考虑基于边的枚举复杂度太高,基于点地统计答案。

做容斥,枚举 \(S\) 中的点,钦定 \(S\) 中的点没有被覆盖,剩下的点集随便有没有被覆盖。

那么一些边被限制不能选中,其它边随意选,统计出端点均不在 \(S\) 中的边的个数 \(C(S)\),答案即 \(\sum (-1)^{|S|}C(S)\),直接做即可做到 \(O(2^n\times m)\)。

后面两个做法均需要此容斥。

做法2(Yet Another Random Solution)

这是我赛时的做法。

考虑将点集划分成 \(A,B\) 两坨,且大小分别为 $\lfloor n/2\rfloor ,\lceil n/2\rceil $,分别对 \(A,B\) 导出子图内部进行上面的容斥,并枚举 \(A,B\) 钦定的情况,再考虑中间的边,若两侧都没有被钦定则有 \(2\) 的系数,否则一定不能选,只有 \(1\),这样直接做是 \(O(2^nm)\) 的,但是注意到我们完成了内部的容斥后只关心 \(A\) 中与 \(B\) 有边的点是否被钦定,称之为 \(La\),同理还有 \(B\) 中与 \(A\) 有边的点集 \(Rb\),我们统计 \(La\) 中被钦定非法的点为 \(SLa\) 的方案数,和 \(Rb\) 中被钦定非法的方案数 \(SLb\) 的方案数,然后仅枚举这两个集合的子集并考虑中间的边的系数。

时间复杂度 \(O((2^{n/2}+2^{|La|+|Rb|})m)\)。

同理,我们大量随机 \(A,B\),取复杂度最小的来跑。

取 \(Test = 10^6\),在大量随机数据及我尝试构造的数据下,在题目数据范围下 \(|La|+|Rb|\) 的最值不会超过 \(16\)。

这玩意甚至能跑 \(m\leq 75\),感觉比做法 1 快了很多,有没有人能讲讲证明/hack 阿。

一个能将本做法卡至相对较高复杂度的数据是两个相对着的菊花,形如 \((1,3),(2,3),(1,4),(2,4)\dots (1,n),(2,n)\),这个时候最优的划分是将 \(1,2\) 划分至同一侧,剩下的点平均划分开,在本题的数据范围下最多有 \(16\) 个点向另一侧有边,需要被考虑。

做法3(超级炫酷爆标确定性做法)

考虑上面容斥,每次枚举一个点并考虑是否钦定,若钦定则删去其周围的边,若不钦定则周围的边的答案仅依赖于连接的另一个点是否钦定,将边挂在它的另一侧即可。故考虑完这个点是否钦定后,我们可以直接删除掉这个点。

直接删除所有点仍然是 \(O(2^n)\) 的,删除一些边缘的点是没啥用的,故我们不断删除度数不小于 \(3\) 的点,最多删除 \(m/3\) 次,接下来剩下的所有点度数不超过 \(2\),故剩下的图是若干环和链(含孤点),这个东西的覆盖是简单的,直接断环为链,对链跑 dp,记录目前点是否钦定,需要乘上那些挂在上面的边的系数。

时间复杂度 \(O(2^{m/3}(n+m))\),故本题的 \(n\) 其实可以开到 \(60\)。

标签:从洛谷,钦定,边覆盖,点集,计数,划分,枚举,做法,复杂度
From: https://www.cnblogs.com/Dreamerkk/p/18240467

相关文章

  • 计数问题(普及)
    描述试计算在区间[1,n]的所有整数中,数字x(0<=x<=9)共出现了多少次?例如,在1到11中,即在1、2、3、4、5、6、7、8、9、10、11中,数字1出现了4次。输入描述共1行,包含2个正整数n、x,之间用一个空格隔开。输出描述共一行,包含一个整数,表示x出现的次数。用例输入1111用例输出14......
  • 计数排序(排序终篇)
    1.计数排序2.排序的稳定性1.计数排序1.1计数排序的概念计数排序就是把要排序的数组的里面的数据在有序的数组中记录次数,每个数据有多少个就在另一个数组(有序的)上对应的位置加多少,有俩个2就在有序的数组下标2的位置标2,最后把有序数组的元素按顺序一个一个搬过来,这样就把......
  • 慢慢写 十二重计数法
    \(n\)球\(m\)​盒。谁家数学答题卡。\(\text{I}\):球之间互不相同,盒子之间互不相同。每个球\(m\)种放法,\(n^m\)。\(\text{II}\):球之间互不相同,盒子之间互不相同,每个盒子至多装一个球。\(n>m\)则\(0\)。\[\binom{m}{n}n!=\frac{m!}{n!(m-n!)}n!=\frac{m!}{(m......
  • JVM之GC篇:(一)引用计数与可达性分析
    文章目录0x00前言0x01引用计数0x02可达性分析0x03总结0x00前言GC的第一步就是要判断出哪些对象需要被回收。显然易见的是,当一个对象不再被使用后,那么就需要对其进行回收。那么问题就是,如何判断对象是否被使用?本文将介绍两种算法来判断对象的使用情况。0x01引......
  • 联想打印机更换硒鼓后仍旧报错,如何做硒鼓计数器清零?
        在联想打印机的使用过程中,硒鼓是一个重要的耗材,它直接影响到打印质量和打印机的运行。通常,当打印机显示硒鼓错误或者打印质量下降时,更换新的硒鼓是一个常见的解决方案。然而,有时候即使更换了新的硒鼓,打印机仍然会报错,这可能是由于硒鼓计数器没有清零导致的。  ......
  • 洛谷P4017 最大食物链计数
    题目信息题目要求样例输入/输出 算法简介 要知道题目需要用到什么样的算法,首先得捋清楚题目的意思比如这个题目,我们读题后可以获得这样的信息:(1)节点之间构成有向边(2)所有边不会构成环(3)需要求的所有的边没有边权而且一定是从入度为零的节点到出度为零的节点基......
  • 八大排序:插入、希尔、冒泡、选择、快速、堆、归并、计数
    目录一、插入排序:二、希尔排序:三、冒泡排序:四、选择排序:五、快速排序:    1、霍尔法:    2、挖坑法:    3、前后指针法:    4、非递归的实现:六、堆排序:七、归并排序:1、递归实现:2、非递归实现:八、计数排序:一、插入排序:插入排序......
  • C# 中科学计数法转成正常值(转)
    抓取数据的时候碰到科学技术法,查了一些资料,直接贴代码///<summary>///数字科学计数法处理///</summary>///<paramname="strData"></param>///<returns></returns>privateDecimalChangeToDecimal(strin......
  • CSP历年复赛题-P1980 [NOIP2013 普及组] 计数问题
    原题链接:https://www.luogu.com.cn/record/160821231题意解读:统计1~n中x的个数。解题思路:枚举每个数,提取每一位,判断是否等于x。100分代码:#include<bits/stdc++.h>usingnamespacestd;intn,x,ans;intmain(){cin>>n>>x;for(inti=1;i<=n;i++)......
  • 眼精星和金鸣识别新增智能结构化识别,助您快速筛选和统计数据
    熟悉眼精星票证识别系统或金鸣表格文字识别大师的用户都知道,近日,这二款软件同时上线了“智能结构化”功能,那么,什么是智能结构化呢?准确地说,我们这里的智能结构化应为OCR智能结构化,因为它主要是用OCR技术来实现的。OCR智能结构化识别(OCRIntelligentStructuredRecognition)是......