我得到了集{1,2,3,...,N}.我必须找到给定集合的子集的最大大小,以便来自子集的任何2个数字的总和不能被给定的数字K整除.N和K可以达到2*10 ^ 9所以我需要一个非常快的算法.我只提出了复杂度为O(K)的算法,这种算法很慢.
我有一个家庭作业问题,我不知道如何解决它.如果你能给我一个想法,我将非常感激.
这就是问题:"给定一个连通的无向图,它有N个顶点和N个边.每个顶点都有成本.你必须找到一个顶点子集,这样子集中顶点的总成本才是最小的,每个边缘都与子集中的至少一个顶点一起入射."
先感谢您!
PS:我已经解决了很长一段时间的解决方案,我想出的唯一想法是回溯或二分图中的最低成本匹配,但这两个想法对于N = 100000都太慢了.