视频讲解

题目内容

调度器上有一组将调度的任务（$job$），大部分任务之间存在亲和关系，需要优先把具有亲和关系的任务调度到同一个核上面，不亲和的任务不能运行在同一个核上面；

现在给定一组待调度的任务（任务编号和任务执行时间），同时会给出任务之间不存在亲和关系的列表（未给出的默认是亲和关系）。请设计一个调度器，按照如下要求：

1、找出一组包含亲和任务数量最多的亲和调度任务组；

塔子哥的小提示

如果考试中遇到此类题型，建议直接使用DFS $O(2^n)$ 暴力计算结果,说不定官方手软，给这种暴力解法70%以上的通过率。所以塔子哥不建议没有竞赛经验的同学死磕正确解法。

思路1:最大团搜索算法

该问题就是最大团搜索算法的模板题。在搜索出每个最大团之后把团内节点的权值累加更新即可

思路2:折半搜索(meet in the mid) + 子集dp