# 14138: 【原4138】选组员

### 题目描述

author: fur 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4138

# 选组员

4 4
2 2
0 1
2 3
1 2
2 4
0 2
3 -9
0 1 2

2.00

## 数据规模

$$n=4$$

$$k_i\leq2$$

$$1\leq n\leq 15$$
$$0\leq m\leq 100$$
$$1\leq k_i\leq min(n,5)$$

## ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

int n, m;
bool visited[20] = { 0 };
int groups[109][20] = { 0 };
int val_data[109] = { 0 };
int val_num[109] = { 0 };

double ans = 0.0;

void cal_max(int pos) {
if (pos == n) {
double cur_ans = 0.0;
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (visited[i]) {
++cnt;
}
}
for (int i = 0; i < m; ++i) {
bool flag = true;
for (int j = 0; j < val_num[i]; ++j) {
if (!visited[groups[i][j]]) {
flag = false;
break;
}
}
if (flag) {
cur_ans += double(val_data[i]);
}
}
if (cnt > 0)
cur_ans /= double(cnt);
ans = cur_ans > ans ? cur_ans : ans;
return;
}
visited[pos] = true;
cal_max(pos + 1);
visited[pos] = false;
cal_max(pos + 1);
}

int main() {
scanf("%d %d", &n, &m);

for (int i = 0; i < m; ++i) {
scanf("%d %d", &val_num[i], &val_data[i]);
for (int j = 0; j < val_num[i]; ++j) {
scanf("%d", &groups[i][j]);
}
}

cal_max(0);
printf("%.2f",ans);

return 0;
}

## WashSwang's solution

#include <iostream>
#include <iomanip>
using namespace std;
int sum,n,m,k[200],c[200],ex[20],num,x;
double ans;
int main() {
cin>>n>>m;
for (int i=0,j=1;i<15;i++,j<<=1) ex[i]=j;
for (int i=0;i<m;++i){
cin>>num>>c[i];
for (int j=0;j<num;++j){
cin>>x;
k[i]+=ex[x];
}
}
for (int i=0;i<(1<<n);++i){
sum=0;
num=0;
for (int j=0;j<m;++j)
if ((i&k[j])==k[j]) sum+=c[j];
for (int j=i;j>0;j>>=1)
if (j%2) num++;
if (num!=0&&sum/double(num)>ans) ans=sum/double(num);
}
cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans;
return 0;
}