1125. 最小的必要团队
作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。
所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。
我们可以用每个人的编号来表示团队中的成员：例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。
请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按任意顺序返回答案，本题保证答案存在。
示例 1：
输入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
输出：[0,2]
示例 2：
输入：req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
输出：[1,2]
题解：很显然的可重覆盖问题了，舞蹈链直接解即可，关于舞蹈链，详见：
当然，本题就面试而言，还是先答一下DP+二进制记录状态。
struct DLX{static const int maxn = 111;static const int maxm = 111;static const int maxnode = maxn*maxm;int n,m,size;int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];int H[maxn],S[maxm];int ansd,ans1[111111], ans[111111];void init(int _n,int _m){n = _n,m = _m;for(int i = 0;i<=m;++i){S[i] = 0;U[i] = D[i] = i;L[i] = i-1;R[i] = i+1; }R[m] = 0,L[0] = m;size = m;for(int i = 1;i<=n;++i)H[i] = -1;}void link(int r,int c){++S[ Col[++size] = c ];Row[size] = r;D[size] = D[c];U[ D[c] ] = size;U[size] = c;D[c] = size;if(H[r] < 0)H[r] = L[size] = R[size] = size;else{R[size] = R[H[r]];L[R[H[r]]] = size;L[size] = H[r];R[H[r]] = size;}}void remove(int c){for(int i = D[c]; i != c;i = D[i])L[ R[i] ] = L[i],R[ L[i] ] = R[i];}void resume(int c){for(int i = U[c]; i != c;i = U[i])L[R[i]] = R[ L[i] ] = i;}bool v[maxm];int f(){int res = 0;for(int c = R[0];c;c = R[c])v[c] = true;for(int c = R[0];c;c=R[c])if(v[c]){res++;v[c] = false;for(int i = D[c];i!=c;i = D[i])for(int j = R[i];j!=i;j = R[j])v[ Col[j] ] = false;}return res;}void dance(int d){if(d+f() >= ansd)return;if(R[0] == 0){if(d < ansd){ansd = d;for(int i = 0;i<d;++i)ans[i] = ans1[i];}return;}int c = R[0];for(int i = R[0];i;i = R[i])if(S[i] < S[c])c = i;for(int i = D[c];i != c;i = D[i]){ans1[d] = Row[i];remove(i);for(int j = R[i];j != i;j = R[j])remove(j);dance(d+1);for(int j = L[i];j != i; j = L[j])resume(j);resume(i);} }
}g;class Solution {
public:vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {unordered_map<string,int> mp;for(int i = 0;i < (int)req_skills.size();++i)mp[req_skills[i]] = i+1;int n = people.size(),m = req_skills.size();g.init(n,m);for(int x = 0;x<(int)people.size();++x){for(int i = 0;i<(int)people[x].size();++i){int y = mp[people[x][i]];g.link(x+1,y);}}g.ansd = 11111111;g.dance(0);vector<int>ans;for(int i = 0;i<g.ansd;++i){ans.push_back(g.ans[i]-1);}return ans;}
};
DP+二进制记录状态：
class Solution {
public:vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {int n = req_skills.size();int full = 1<<n;unordered_map<string,int> skills;vector<int> dp(full,-1);unordered_map<int,vector<int>> team;/*initial*/for(int i = 0;i < n; ++i){skills[req_skills[i]] = i;}dp[0] = 0;team[0] = vector<int>();for(int i = 0;i < people.size(); ++i){int idx = 0;for(auto s : people[i]){if(skills.count(s)){idx = idx|(1<<skills[s]);}}for(int j = 0;j < full; ++j){if(dp[j] >= 0){int x = j|idx;if(dp[x] == -1 || dp[x] > dp[j] + 1){dp[x] = dp[j] + 1;team[x] = team[j];team[x].push_back(i);}}}}return team[full-1];}
};