塔子哥的小提示

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

思路1:最大团搜索算法

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

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

前置知识:二进制枚举技巧

一个最简单的思路就是$O(2^n)$枚举所有子集，但是这样复杂度超了。我们观察到$n = 30$ , 自然想到可以将集合分成两个部分$|A| = |B| = 15$ ， 这样我们就可以分别对$|A| , |B|$ 暴力计算最大亲和的子集了.

此时的问题在于：如何解决$A,B$ 集合之间的不亲和情况。

例如来自$A$集合的$1001$ , 那也就是第1,4个节点被选中，假设他们对于B集合的第2，3个点不亲和。那么也就是二进制状态$0110$不亲和。反过来也就是$1001$亲和。那么我们就只需要求出$B$集合在$1001$限定状态下最多能互相亲和的个数。

这个个数可以使用子集$dp$求出，如果s本身就是亲和的，那么$dp[s] = |s|$ , 也就是s中二进制个数。

否则，考虑$dp[s] = max(dp[x])$ , x是s的真子集。且x二进制中个数恰好比s少1。 复杂度$O(2^{|A|})$

最后枚举$A$集合的亲和子集，匹配B集合的dp ， 加起来即可。总复杂度$O(2^{\frac{n}{2}})$ 。

最大团思路

MAX_N = 31  # 最大顶点数为31

# 初始化邻接矩阵,记录哪些顶点之间存在边
adjacency_matrix = [[False for _ in range(MAX_N)] for _ in range(MAX_N)]

# 存储一些顶点的信息
some_vertices = [[0 for _ in range(MAX_N)] for _ in range(MAX_N)]
none_vertices = [[0 for _ in range(MAX_N)] for _ in range(MAX_N)]
all_vertices = [[0 for _ in range(MAX_N)] for _ in range(MAX_N)]
vertex_values = [0] * MAX_N  # 存储每个顶点的权值

answer_size = 0  # 最大团的大小
answer_sum = 0  # 最大团中所有顶点权值之和

def dfs(depth, selected_count, some_count, none_count):
    global answer_size, answer_sum
    # 当没有"some"顶点和"none"顶点时,说明找到了一个最大团
    if some_count == 0 and none_count == 0:
        current_sum = 0
        for i in range(selected_count):
            current_sum += vertex_values[all_vertices[depth][i]]
        # 更新最大团的大小和权值之和
        if answer_size < depth:
            answer_size = depth
            answer_sum = float('inf')
        if answer_size == depth:
            answer_sum = min(answer_sum, current_sum)
        return

    start_vertex = some_vertices[depth][0]
    for i in range(some_count):
        vertex = some_vertices[depth][i]
        # 如果当前顶点与上一个"some"顶点存在边,则跳过
        if adjacency_matrix[start_vertex][vertex]:
            continue
        # 将当前顶点添加到当前选择的顶点集合中
        for j in range(selected_count):
            all_vertices[depth + 1][j] = all_vertices[depth][j]
        all_vertices[depth + 1][selected_count] = vertex
        new_some_count, new_none_count = 0, 0
        # 更新"some"和"none"顶点集合
        for j in range(some_count):
            if adjacency_matrix[vertex][some_vertices[depth][j]]:
                some_vertices[depth + 1][new_some_count] = some_vertices[depth][j]
                new_some_count += 1
        for j in range(none_count):
            if adjacency_matrix[vertex][none_vertices[depth][j]]:
                none_vertices[depth + 1][new_none_count] = none_vertices[depth][j]
                new_none_count += 1
        # 递归调用DFS
        dfs(depth + 1, selected_count + 1, new_some_count, new_none_count)
        # 将当前顶点从"some"集合移动到"none"集合
        some_vertices[depth][i] = 0
        none_vertices[depth][none_count] = vertex
        none_count += 1

if __name__ == "__main__":
    n = int(input())  # 读取顶点数
    vertex_values = [0] + list(map(int, input().split()))  # 读取每个顶点的权值
    m = int(input())  # 读取边数
    # 初始化邻接矩阵
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i != j:
                adjacency_matrix[i][j] = True
    # 读取边的信息,并更新邻接矩阵
    for i in range(1, m + 1):
        u, v = map(int, input().split())
        adjacency_matrix[u][v] = adjacency_matrix[v][u] = False
    # 初始化"some"顶点集合
    for i in range(n):
        some_vertices[1][i] = i + 1
    # 调用DFS函数
    dfs(1, 0, n, 0)
    print(answer_sum)  # 输出最大团中所有顶点权值之和

meet in the mid + 子集和dp

n = int(input())
time = [0] + list(map(int, input().split())) # 读入每个点的时间
edge = [[] for _ in range(n + 1)] # 记录每个点的边
edge_num = int(input()) # 读入边的数量
for i in range(edge_num): # 读入边
    u, v = map(int, input().split())
    if u == v:
        continue
    edge[u].append(v)
    edge[v].append(u)
num_A = n // 2 # A集合的点数和B集合的点数 以及集合的大小
size_A = 1 << num_A
num_B = n - num_A
size_B = 1 << num_B
def map_to (i , offest):
    return i + offest
# 计算A集合和B集合的好子集
def calc_good_subset(edge , num , sz, offset):
    is_good_subset = [False] * sz
    is_good_subset[0] = True
    subset_sum = [0] * sz
    # 遍历所有的子集
    for i in range(sz):
        subset = []
        # 计算子集的时间和
        for j in range(num):
            if i >> j & 1:
                subset.append(j + 1)
                subset_sum[i] += time[map_to(j + 1, offset)]
        good = True
        # 判断子集是否合法 , 即子集中的点之间没有边
        for j in subset:
            for k in subset:
                if map_to(k , offset) in edge[map_to(j , offset)]:
                    good = False
                    break
        # 如果合法则标记为True
        if good:
            is_good_subset[i] = True
    return is_good_subset , subset_sum
# 计算A集合和B集合的好子集以及时间和
is_good_subset_A , sum_A = calc_good_subset(edge , num_A , size_A ,0)
is_good_subset_B , sum_B = calc_good_subset(edge , n - num_A , size_B , num_A)

# 计算二进制中1的个数
def get_bits (x):
    res = 0
    while x:
        res += x & 1
        x >>= 1
    return res

# dp转移出B集合的信息，包括i以及他的子集的状态下最多的点数和在保持最多点数情况下的最小的时间和
subset_info = [[-10**9 , 10**9] for _ in range(size_B)]
subset_info[0] = [0 , 0]
for i in range(size_B):
    if is_good_subset_B[i]:
        subset_info[i] = [get_bits(i) , sum_B[i]]
    for j in range(num_B):
        if i >> j & 1:
            g = i ^ (1 << j) # 去掉j这个点
            # 先考虑点的个数尽量多的
            if subset_info[i][0] < subset_info[g][0]:
                subset_info[i][0] = subset_info[g][0]
                subset_info[i][1] = subset_info[g][1]
            # 点的个数相同的情况下，考虑时间总和小的
            elif subset_info[i][0] == subset_info[g][0]:
                if subset_info[i][1] > subset_info[g][1]:
                    subset_info[i][1] = subset_info[g][1]


# 考虑合并A集合和B集合的冲突
max_num = -1
min_sum = 10**9
for i in range(size_A):
    if not is_good_subset_A[i]:
        continue
    subset = []
    for j in range(num_A):
        if (i >> j & 1) == 0:
            continue
        subset.append(j + 1)
    # 计算B集合的好状态
    good_states = (1 << num_B) - 1
    for j in subset:
        # 如果A集合中的点和B集合中的点有冲突，则去掉B集合中的点
        for k in edge[j]:
            # 如果k在B集合中
            if k > num_A:
                # 如果k在B集合中的点和A集合中的点有冲突
                if (good_states >> (k - num_A - 1)) & 1:
                    # ban掉k这个点
                    good_states ^= 1 << (k - num_A - 1)
    # 去掉A集合中的点,只保留B集合中的点
    num = get_bits(i) + subset_info[good_states][0]
    tot_s = sum_A[i] + subset_info[good_states][1]
    # 如果点数更多或者点数相同但是时间更少
    if max_num < num or (max_num == num and min_sum > tot_s):
        max_num = num
        min_sum = tot_s
print(min_sum)

c++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <climits>
#include <algorithm>

using namespace std;

int jobNum;
vector<int> times;
unordered_map<int, unordered_set<int>> mutex;
int ans = 1;
int cost = INT_MAX;

bool check(int i, const unordered_set<int>& usd) {
    for (int u : usd) {
        if (mutex[u].count(i) || mutex[i].count(u)) return false;
    }
    return true;
}

void dfs(int i, unordered_set<int>& usd, int time) {
   //停止条件
    if (i >= jobNum) {
        if (ans <= (int)usd.size()) {
            if (ans < (int)usd.size()) {
                ans = usd.size();
                cost = time;
            } else if (ans == (int)usd.size()) {
                if (time < cost) {
                    cost = time;
                }
            }
        }
        return;
    }
    if (usd.size() + jobNum - i + 1 < ans) return ;
    dfs(i + 1, usd, time);
    if (check(i, usd)) {
        usd.insert(i);
        dfs(i + 1, usd, time + times[i]);
        usd.erase(i);
    }
}

int main() {
    cin.tie(0);
    cin >> jobNum;
    times.resize(jobNum);
    for (int i = 0; i < jobNum; i++) {
        cin >> times[i];
    }

    int mutexNum;
    cin >> mutexNum;

    for (int i = 0; i < mutexNum; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        mutex[a].insert(b);
        mutex[b].insert(a);
    }

    unordered_set<int> usd;
    dfs(0, usd, 0);

    cout << cost << endl;

    return 0;
}

视频讲解

题目内容

调度器上有一组将调度的任务（$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$。