华为8.21笔试题

第三题：主要是不亲和关系的存储，其余部分通过回溯即可解决

#include<bits/stdc++.h>

using namespace std;

const int N = 35;
int t[N];
int n;
unordered_map<int, unordered_set<int>>mp;
int cost = INT_MAX, ans = 0;

bool check(int u, unordered_set<int>&used){
    for(auto x : used){
        if(mp[x].count(u) || mp[u].count(x)){
            return false;
        } 
    }
    return true;
}

void dfs(int u, unordered_set<int>&used, int time){
    if(u > n){
        if(ans <= (int)used.size()){
            if(ans < (int)used.size()){
                ans = used.size();
                cost = time;
            }
            else if(ans == (int)used.size()){
                if(time < cost){
                    cost = time;
                }
            }
        }
        return ;
    }
    if(n - u  + 1 + (int)used.size() < ans) return ;
    dfs(u + 1, used, time);
    if(check(u, used)){
        used.insert(u);
        time += t[u];
        dfs(u + 1, used, time);
        time -= t[u];
        used.erase(u);
    }
}

int main(){
    cin>>n;
    for(int i = 1; i <= n; i ++){
        cin>>t[i];
    }
    int k;
    cin>>k;
    for(int i = 0; i < k; i ++){
        int u, v;
        cin>>u>>v;
        mp[u].insert(v);
        mp[v].insert(u);
    }
    unordered_set<int>used;
    dfs(1, used, 0);
    cout<<cost<<endl;

    return 0;
}