题意：m种职业，每种职业都有某些技能。每个人属于不同职业，用p个人组成ans（数目最多）个队伍，满足每个队伍每个技能都被拥有。
特殊：职业与职业之间，要么完全不相交，要么是包含关系。
思路：按照职业的包含关系建立一棵树，问题就被分解为多个子问题。简化一下问题，想象这棵树上第一层（没有别的职业包含它）每个职业Ki，并且这棵树只有这一层，总的队伍数，就是min（Ki职业的人数），取min（Ki职业的人数）的前提是，K1……Km所覆盖的技能数是n。那么这样选择后，可以等价于产生了一个新的职业K0，他们拥有所有的技能，他们的人数是min（Ki职业的人数）。解决这个问题，我们可以把这棵树上所有节点都看成一个子问题，直接dfs解决。
同样，输出方案的方法也是dfs
这个代码过了 Kattis-team up vjudege：Team-up
但是没过UVALive
很气啊
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 #include <iostream> 5 #include <vector> 6 #include <cstring> 7 #define inf 0x3f3f3f3f 8 using namespace std; 9 int skill_size[300033]; 10 vector<int> skill[100033]; 11 vector<int> G[300033]; 12 vector<int> P[300033]; 13 vector<int> ans[300033]; 14 int fa[300033]; 15 bool cmp(int a,int b) 16 { 17 return skill_size[a]<skill_size[b]; 18 } 19 int n,m,p; 20 int dfs(int u) 21 { 22 int t = 0;int tans = 1e9; 23 for (unsigned int i = 0; i<G[u].size(); i++) 24 { 25 int v = G[u][i]; 26 t+=skill_size[v]; 27 tans = min(tans,dfs(v)); 28 } 29 return P[u].size() + (t==skill_size[u]?tans:0); 30 } 31 void print(int u , int num) 32 { 33 if (num <= 0) return; 34 for (unsigned int i = 0; i<P[u].size() ;i++) 35 if (num-i>=1) ans[num - i].push_back(P[u][i]); 36 else break; 37 for (unsigned int i = 0; i<G[u].size();i++) 38 if ((unsigned int)num > P[u].size()) print(G[u][i],num-P[u].size()); 39 else break; 40 } 41 int main() 42 { 43 int a,d; 44 while (~scanf("%d%d%d",&n,&m,&p)) 45 { 46 memset(fa,-1,sizeof(fa)); 47 for (int i = 0;i<=n;i++) skill[i].clear(); 48 for (int i = 0;i<=m;i++) G[i].clear(); 49 for (int i = 0;i<=m;i++) P[i].clear(); 50 for (int i = 0;i<=p;i++) ans[i].clear(); 51 for (int i = 1; i<=m; i++) 52 { 53 scanf("%d",&a); 54 skill_size[i] = a; 55 while (a--) 56 { 57 scanf("%d",&d); 58 skill[d].push_back(i); 59 } 60 } 61 for (int i = 1;i<=n; i++) 62 { 63 sort(skill[i].begin(),skill[i].end(),cmp); 64 for ( int j = 0; j<((int)skill[i].size())-1;j++) 65 { 66 if (fa[skill[i][j]]==-1) 67 { 68 fa[skill[i][j]] = skill[i][j+1]; 69 G[skill[i][j+1]].push_back(skill[i][j]); 70 } 71 } 72 if (skill[i].size()==0) continue; 73 int la = skill[i][skill[i].size()-1]; 74 if (fa[la] == -1) 75 { 76 fa[la] = 1; 77 G[0].push_back(la); 78 } 79 } 80 for (int i = 1;i<=p; i++) 81 { 82 scanf("%d",&a); 83 P[a].push_back(i); 84 } 85 skill_size[0] = n; 86 int Ans = dfs(0); 87 printf("%d ",Ans); 88 print(0,Ans); 89 for (int i = 1;i<=Ans;i++) 90 { 91 printf("%d",ans[i].size()); 92 for (unsigned int j = 0; j<ans[i].size();j++) 93 { 94 printf(" %d",ans[i][j]); 95 } 96 puts(""); 97 } 98 } 99 return 0; 100 }