1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <climits> 5 #include <cctype> 6 #include <cmath> 7 #include <string> 8 #include <sstream> 9 #include <iostream>10 #include <algorithm>11 #include <iomanip>12 using namespace std;13 #include <queue>14 #include <stack>15 #include <vector>16 #include <deque>17 #include <set>18 #include <map>19 typedef long long LL;20 typedef long double LD;21 #define pi acos(-1.0)22 #define lson l, m, rt<<123 #define rson m+1, r, rt<<1|124 typedef pair<int, int> PI;25 typedef pair<int, PI> PP;26 #ifdef _WIN3227 #define LLD "%I64d"28 #else29 #define LLD "%lld"30 #endif31 //#pragma comment(linker, "/STACK:1024000000,1024000000")32 //LL quick(LL a, LL b){LL ans=1;while(b){if(b & 1)ans*=a;a=a*a;b>>=1;}return ans;}33 //inline int read(){char ch=‘ ‘;int ans=0;while(ch<‘0‘ || ch>‘9‘)ch=getchar();while(ch<=‘9‘ && ch>=‘0‘){ans=ans*10+ch-‘0‘;ch=getchar();}return ans;}34 //inline void print(LL x){printf(LLD, x);puts("");}35 //inline void read(double &x){char c = getchar();while(c < ‘0‘) c = getchar();x = c - ‘0‘; c = getchar();while(c >= ‘0‘){x = x * 10 + (c - ‘0‘); c = getchar();}}36 37 int a[20], b[20];38 int cost[1<<15], order[1<<15], dp[1<<15];39 int main()40 {41 #ifndef ONLINE_JUDGE42     freopen("in.txt", "r", stdin);43     freopen("out.txt", "w", stdout);44 #endif45     int t;46     scanf("%d", &t);47     while(t--)48     {49         int n, m;50         scanf("%d%d", &n, &m);51         for(int i=0;i<n;i++)52             scanf("%d", &a[i]);53         for(int i=0;i<n;i++)54             scanf("%d", &b[i]);55         memset(order, 0, sizeof(order));56         for(int i=0;i<n;i++)57         {58             int x;59             scanf("%d", &x);60             while(x--)61             {62                 int y;63                 scanf("%d", &y);64                 order[i]|=(1<<(y-1));65             }66         }67         int ans=0;68         memset(dp, -1, sizeof(dp));69         memset(cost, 0, sizeof(cost));70         dp[0]=0;71         for(int i=0;i<(1<<n);i++)72             for(int j=0;j<n;j++)73                 if(i & (1<<j))74                     cost[i]+=b[j];75         for(int i=0;i<(1<<n);i++)76         {77             if(dp[i]==-1)78                 continue;79             for(int j=0;j<n;j++)  // i状态能否从j状态转移过来80                 if((i & order[j])==order[j] && cost[i]+b[j]<=m && (i & (1<<j))==0)81                 {  //顺序是否满足                  花费是否满足        第i个是否已经吃掉82                     dp[(1<<j)|i]=dp[i]+a[j];83                     ans=max(ans, dp[(1<<j)|i]);84                 }85         }86         printf("%d\n", ans);87     }88     return 0;89 }90 91 HDU 3182