塔子哥的小提示

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

思路1:最大团搜索算法

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

视频讲解

题目内容

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

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

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

2、如果规则$1$有多个解，给出所有任务执行时间之和最小的。并输出该亲和调度任务组的所有任务执行时间之和。

亲和调度任务组定义：一组可以在同一核上面执行的亲和任务集合

解答要求

时间限制 $C/C++1000ms$ ，其他语言:$2000ms$ 内存限制 $C/C++256MB$，其他语言:$512MB$

输入

首行是一个整数$jobNum$，表示任务数量，任务编号$[1，jobNum]$，取值范围$[1,30]$

第二行$jobNum$个整数，表示每个任务的执行时间

第三行是一个整数$mutexNum$，表示不存在亲和关系的列表个数

接下来$mutexNum$行，每一行表示$1$对不亲和的任务编号，任务编号范围$[1,jobNum]$

输出

一个整数，表示所有任务的最短执行时间。

样例1

输入

3
2 3 10
1 
1 2

输出

12

解释:有$3$个待调度任务，任务$1$和任务$2$不亲和，不能在一个核上执行；

1.亲和调度任务组有：“任务$1$”“任务$2$”“任务$3$”，“任务$1$+任务$3$”，“任务$2$+任务$3$”；

2.包含任务数量最参的亲和调度任务组合有两种:“任务$1$+任务$3$”，或“任务$2$+任务$3$”；

3.两个任务的执行时间分别为$12$和$13$，选样执行时间较小的“任务$1$+任务$3$”，输出$12$。

样例2

输入

1
1
0

输出

1

解释:只有一个任务，返回这个任务的执行时间。

样例3

输入

3
2 3 10
3
1 2
2 3
1 3

输出

2

解释：有$3$个待调度任务，任务$1$和任务$2$、任务$2$和任务$3$、任务$1$和任务$3$不亲和，不能在一个核上执行；

1、亲和调度任务组有:“任务$1$”，“任务$2$”，“任务$3$”；

2、包含任务数量最多的亲和调度任务组合有$3$种:“任务$1$”，“任务$2$”，“任务$3$”；

3、$3$个场景的执行时间分别为$2、3、10$，选择执行时间较小的“任务$1$”，输出$2$。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写