HDU - 6006 Engineer Assignment (状压dfs)
2024-09-02 08:23:44
题意: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;
}
最新文章
- 通过实战理解C语言精要——函数篇
- java工程中的.classpath<;转载>;
- uva 11380(最大流+拆点)
- git push -u origin master 上传出错问题
- oracle使用口令文件验证和os验证
- 修改Jenkins用户的密码
- 基于puppeteer模拟登录抓取页面
- 【转】priority_queue优先队列
- Python基础与进阶
- 创作型---原型模式(C# ICloneable接口的实现)
- 【JSOI2008】火星人prefix 哈希 非旋转treap
- 11.6 正睿停课训练 Day17
- WWSSN instrument response
- EF利用重写SaveChanges()方法实现 审计日志记录
- JAVA JMX协议监控
- URAL 1963 Kite 计算几何
- spark shuffle内在原理说明
- 执行存储过程报错——ora-01031:权限不足
- jmeter之beanshell断言---数据处理
- BZOJ 1036 树的统计Count 树链剖分模板题