回溯和部分剪枝，ac全过，复杂的题库可能会超时。

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

using namespace std;
vector<int> path;
vector<vector<int>> res;
int maxNum = 0;

void dfs(int index, int n, unordered_map<int, vector<int>>& map) {
    //实现部分剪枝
    if (path.size() >= maxNum) {
        res.push_back(path);
        maxNum = path.size();
    }

    for (int i = index + 1; i <= n; i++) {
        int flag = 0;
        for (int j = 0; j < path.size(); j++) {
            for (int p = 0; p < map[path[j]].size(); p++) {
                if (map[path[j]][p] == i) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1) {
                break;
            }
        }
        //当前序号与path中元素都不冲突，则加入path
        if (flag == 0) {
            path.push_back(i);
            dfs(i, n, map);
            path.pop_back();
        }
    }

}
int main() {
    int n;
    cin >> n;

    vector<int> jobtime(n);
    for (int i = 0; i < n; i++) {
        cin >> jobtime[i];
    }

    int mu;
    cin >> mu;
    //用map记录非亲和关系
    unordered_map<int, vector<int>> map;
    for (int i = 0; i < mu; i++) {
        int a, b;
        cin >> a >> b;
        map[a - 1].push_back(b - 1);
        map[b - 1].push_back(a - 1);
    }

    for (int i = 0; i < n; i++) {
        path.push_back(i);
        dfs(i, n-1, map);
        path.clear();
    }

    int sum = INT_MAX;
    for (int i = 0; i < res.size(); i++) {
        if (res[i].size() == maxNum) {
            int tmp = 0;
            for (int a : res[i]) {
                tmp += jobtime[a];
            }
            sum = min(sum, tmp);
        }
    }

    cout << sum << endl;
    return 0;
}

再更新一下，笑死，其实不用维护X数组也行

#include<bits/stdc++.h>
using namespace std;
// 存储图的邻接矩阵表示
vector<vector<bool>> adjMatrix;
// 存储找到的极大团
vector<vector<int>> cliques;
// 深度优先搜索函数，用于找到极大团
void bronKerbosch(vector<int> R, vector<int> P) {
    if (P.empty() ) {
        cliques.push_back(R);
        return;
    }
    int u = -1;
    int maxDegree = -1;
    // 选择度数最大的点作为关键点
    for (int v : P) {
        int degree = 0;
        for (int w : P) {
            if (adjMatrix[v][w]) degree++;
        }
        if (degree > maxDegree) {
            u = v;
            maxDegree = degree;
        } 
    }
    for (int i = 0; i <(int) P.size(); ++i) {
        int v = P[i];
        if (adjMatrix[u][v]) continue;
        vector<int> newR = R;
        newR.push_back(v);
        vector<int> newP;
        for (int w : P) {
            if (adjMatrix[v][w]) newP.push_back(w);
        }
        bronKerbosch(newR, newP);
    }
}

int main() {
    int n, m;
    cin >> n;
    adjMatrix.resize(n+10, vector<bool>(n+10));
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=n;j++)if(i!=j)adjMatrix[i][j]=1;
    for(int i=1;i<=m;i++){
    	int a,b;
    	cin>>a>>b;
    	adjMatrix[a][b]=0;
    	adjMatrix[b][a]=0;
	}
    vector<int> allNodes;
    for (int i = 1; i <= n; ++i) {
        allNodes.push_back(i);
    }
    bronKerbosch({}, allNodes);
    int maxv=0,ans=1e9;
    for(vector<int>&x:cliques){
    	maxv=max(maxv,(int)x.size());
	}
	for(auto&x:cliques){
		if((int)x.size()==maxv){
			int sum=0;
			for(auto&y:x){
				sum+=a[y];
			}
			ans=min(ans,sum);
		}
	}
	cout<<ans;
    return 0;
}

最大团问题，BronKerbosch算法解法：建原图的补图，然后跑最大团就行…

#include<bits/stdc++.h>
using namespace std;
// 存储图的邻接矩阵表示
vector<vector<bool>> adjMatrix;
// 存储找到的极大团
vector<vector<int>> cliques;
// 深度优先搜索函数，用于找到极大团
void bronKerbosch(vector<int> R, vector<int> P, vector<int> X) {
    if (P.empty() && X.empty()) {
        cliques.push_back(R);
        return;
    }
    int u = -1;
    int maxDegree = -1;
    // 选择度数最大的点作为关键点
    for (int v : P) {
        int degree = 0;
        for (int w : P) {
            if (adjMatrix[v][w]) degree++;
        }
        if (degree > maxDegree) {
            u = v;
            maxDegree = degree;
        } 
    }
    for (int i = 0; i <(int) P.size(); ++i) {
        int v = P[i];
        if (adjMatrix[u][v]) continue;
        vector<int> newR = R;
        newR.push_back(v);
        vector<int> newP;
        vector<int> newX;
        for (int w : P) {
            if (adjMatrix[v][w]) newP.push_back(w);
        }
        for (int w : X) {
            if (adjMatrix[v][w]) newX.push_back(w);
        }
        bronKerbosch(newR, newP, newX);
        X.push_back(v);
    }
}

int main() {
    int n, m;
    cin >> n;
    adjMatrix.resize(n+10, vector<bool>(n+10));
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=n;j++)if(i!=j)adjMatrix[i][j]=1;
    for(int i=1;i<=m;i++){
    	int a,b;
    	cin>>a>>b;
    	adjMatrix[a][b]=0;
    	adjMatrix[b][a]=0;
	}
    vector<int> allNodes;
    for (int i = 1; i <= n; ++i) {
        allNodes.push_back(i);
    }
    bronKerbosch({}, allNodes, {});
    int maxv=0,ans=1e9;
    for(vector<int>&x:cliques){
    	maxv=max(maxv,(int)x.size());
	}
	for(auto&x:cliques){
		if((int)x.size()==maxv){
			int sum=0;
			for(auto&y:x){
				sum+=a[y];
			}
			ans=min(ans,sum);
		}
	}
	cout<<ans;
    return 0;
}

DFS解法 通过85% 可以参考一下

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int N = 35;

typedef pair<int, int> pii;
unordered_map<int, int> times;
// 子集问题
vector<vector<int>> res;
vector<int> track;

void backtrack(int N, int start) {
    res.push_back(track);
    for (int i = start; i <= N; i++) {
        track.push_back(i);
        backtrack(N, i + 1);
        track.pop_back();
    }
}

vector<vector<int>> getSub(int N) {
    backtrack(N, 1);
    return res;
}

int main() {
    int num; cin >> num;
    
    for (int i = 1; i <= num; i++) {
        cin >> times[i];
    }
    int mutex;
    cin >> mutex;
    vector<pii> mutex_gp(mutex);
    for (int i = 0; i < mutex; i++) {
        cin >> mutex_gp[i].first >> mutex_gp[i].second;
    }
    vector<vector<int>> all = getSub(num);
    vector<vector<int>> leave; // vec, sz
    int max_num = INT_MIN; // 找到最多点的大小

    for (int i = 0; i < all.size(); i++) {
        // 剪枝
        int flag = 0;
        bool find_l = false, find_r = false;
        if (all[i].size() == 0) continue;
        if (all[i].size() == 1) {
            leave.push_back(all[i]);
            continue;
        } else {
            for (int j = 0; j < mutex_gp.size(); j++) {
                int l = mutex_gp[j].first, r = mutex_gp[j].second;
                // cout << "mutex: " << l << " " << r <<  " all: "; 
                // for (auto val: all[i]) cout << val << "  ";
                // cout << "------";
                for (auto val: all[i]) {
                    if (val == l) find_l = true;
                    if (val == r) find_r = true;
                }
                // cout  << "flag: " << flag <<  endl;
                if (find_l && find_r) {
                    break;
                }
                find_l = false;
                find_r = false;
            }
            if (find_l && find_r) {
                continue; // 过滤掉该元素
            }      
            //  找到最多点 如果数量相同
            // for (auto v: all[i]) cout << v << " ";
            // cout << endl;
            leave.push_back(all[i]);
            int sz = all[i].size();
            // max_num = max(max_num, sz); 
        }

    }
    // 更新时间元素 & 将相关点加入到
    for (int i = 0; i < leave.size(); i++) {
        int n = leave[i].size();
        max_num = max(max_num, n);
    }
    // cout << "max_num: " << max_num << endl;
    vector<int> res;
    for (int i = 0; i < leave.size(); i++) {
        if (max_num == leave[i].size()) {
            int consume = 0;
            for (auto& u: leave[i]) {
                if (times.count(u)) {
                    consume += times[u];
                }
            }
            res.push_back(consume);
        }
    }
    // for (int i = 0; i < res.size(); i++) {
    //     cout << res[i] << " ";
    // }
    if (res.size() > 1) {
        int min_val = INT_MAX;
        for (auto val: res) {
            if (min_val > val) {
                min_val = val;
            }
        }
        cout << min_val << endl;
    } else {
        cout << res[0] << endl;
    }
    return 0;
}

塔子哥的小提示

如果考试中遇到此类题型，建议直接使用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;
}