题意:n个工作,m个人完成,每个工作有ci个阶段,一个人只能选择一种工作完成,可以不选,且只能完成该工作中与自身标号相同的工作阶段,问最多能完成几种工作。

分析:

1、如果一个工作中的某个工作阶段没有任何一个人能完成,则这个工作是不可完成的。

2、预处理每个人能完成各工作的各工作阶段。

3、剪枝:如果当前完成工作数+剩余人数<=ans则剪枝。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define lowbit(x) (x & (-x))
const double eps = 1e-8;
inline int dcmp(double a, double b){
if(fabs(a - b) < eps) return 0;
return a > b ? 1 : -1;
}
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 10 + 10;
const int MAXT = 10000 + 10;
using namespace std;
vector<int> t[MAXN], project[MAXN];
vector<int> engineer[MAXN];
int status[MAXN];
int work[MAXN][MAXN];
int ans;
int n, m;
map<int, int> mp;
int projectnum;
void dfs(int cur, int done){
if(done + m - (cur - 1) <= ans) return;
if(cur == m + 1){
ans = max(ans, done);
return;
}
dfs(cur + 1, done);
for(int i = 1; i <= projectnum; ++i){
int len = project[i].size();
if(status[i] == (1 << len) - 1) continue;
int tmp = status[i];
status[i] |= work[cur][i];
if(status[i] == (1 << len) - 1){
dfs(cur + 1, done + 1);
}
else{
dfs(cur + 1, done);
}
status[i] = tmp;
}
}
void have(int x, int y){
int len1 = engineer[x].size();
int len2 = project[y].size();
for(int i = 0; i < len2; ++i){
bool ok = false;
for(int j = 0; j < len1; ++j){
if(engineer[x][j] == project[y][i]){
ok = true;
break;
}
}
if(ok) work[x][y] |= (1 << i);
}
}
int main(){
int T;
scanf("%d", &T);
int kase = 0;
while(T--){
mp.clear();
ans = 0;
for(int i = 0; i < MAXN; ++i){
project[i].clear();
engineer[i].clear();
t[i].clear();
}
memset(work, 0, sizeof work);
memset(status, 0, sizeof status);
scanf("%d%d", &n, &m);
int k, x;
for(int i = 1; i <= n; ++i){
scanf("%d", &k);
for(int j = 0; j < k; ++j){
scanf("%d", &x);
t[i].push_back(x);
}
}
for(int i = 1; i <= m; ++i){
scanf("%d", &k);
for(int j = 0; j < k; ++j){
scanf("%d", &x);
mp[x] = 1;
engineer[i].push_back(x);
}
}
projectnum = 0;
for(int i = 1; i <= n; ++i){
int l = t[i].size();
bool ok = true;
for(int j = 0; j < l; ++j){
if(!mp.count(t[i][j])){
ok = false;
break;
}
}
if(ok) project[++projectnum] = t[i];
}
for(int i = 1; i <= m; ++i){
for(int j = 1; j <= projectnum; ++j){
have(i, j);
}
}
dfs(1, 0);
printf("Case #%d: %d\n", ++kase, ans);
}
return 0;
}

  

最新文章

  1. 通过实战理解C语言精要——函数篇
  2. java工程中的.classpath&lt;转载&gt;
  3. uva 11380(最大流+拆点)
  4. git push -u origin master 上传出错问题
  5. oracle使用口令文件验证和os验证
  6. 修改Jenkins用户的密码
  7. 基于puppeteer模拟登录抓取页面
  8. 【转】priority_queue优先队列
  9. Python基础与进阶
  10. 创作型---原型模式(C# ICloneable接口的实现)
  11. 【JSOI2008】火星人prefix 哈希 非旋转treap
  12. 11.6 正睿停课训练 Day17
  13. WWSSN instrument response
  14. EF利用重写SaveChanges()方法实现 审计日志记录
  15. JAVA JMX协议监控
  16. URAL 1963 Kite 计算几何
  17. spark shuffle内在原理说明
  18. 执行存储过程报错——ora-01031:权限不足
  19. jmeter之beanshell断言---数据处理
  20. BZOJ 1036 树的统计Count 树链剖分模板题

热门文章

  1. 【PAT甲级】1030 Travel Plan (30 分)(SPFA,DFS)
  2. 使用git下载一个项目
  3. windows 批量杀进程 类似pkill
  4. Python 面试问答基础篇
  5. python多线程采集图片
  6. Sublime设置html头部
  7. leetcode刷题-- 1. 双指针
  8. python面向对象之元类
  9. 吴裕雄--天生自然HADOOP学习笔记:使用yum安装更新软件
  10. Android中利用正则表达式验证手机号是否合法