#include "cstdio"
#include "cmath"
#include "fstream"
#include "cstring"
#include "algorithm"
#include "iostream"
#include "vector"
#include "queue"
#include "stack"
#include "set"
#include "map"
#define lson root<<1
#define rson root<<1|1
#define lowbit(i) i&(-i)
#define debug(x) cout<<#x<<"="<<x<<endl;
#define here cout<<endl<<"_______________here "<<endl;
#define INF 0x7f7f7f7f
#define LINF 0x7f7f7f7f7f7f7f7f
#define Prime 999983
#define N 12
using namespace std;
struct
{
int a, b, c, d, e, f;
int maxa, maxb, maxc, maxd, maxe, maxf;
}sk[N];
int dp[1<<N][7];
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
int T, n, maxx;
scanf("%d", &T);
while(T--)
{
maxx = 0;
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d%d%d%d%d%d", &sk[i].a, &sk[i].b, &sk[i].c, &sk[i].d, &sk[i].e, &sk[i].f);
sk[i].maxa = max(max(sk[i].b, sk[i].c), max(sk[i].d, sk[i].e));
sk[i].maxb = max(max(sk[i].a, sk[i].c), max(sk[i].e, sk[i].f));
sk[i].maxc = max(max(sk[i].a, sk[i].b), max(sk[i].d, sk[i].f));
sk[i].maxd = max(max(sk[i].a, sk[i].c), max(sk[i].e, sk[i].f));
sk[i].maxe = max(max(sk[i].a, sk[i].b), max(sk[i].d, sk[i].f));
sk[i].maxf = max(max(sk[i].b, sk[i].c), max(sk[i].d, sk[i].e));
}
memset(dp, 0, sizeof(dp));
for(int i = 0; i < n; i++)
{
dp[1<<i][sk[i].a] = max(dp[1<<i][sk[i].a], sk[i].maxa);
dp[1<<i][sk[i].b] = max(dp[1<<i][sk[i].b], sk[i].maxb);
dp[1<<i][sk[i].c] = max(dp[1<<i][sk[i].c], sk[i].maxc);
dp[1<<i][sk[i].d] = max(dp[1<<i][sk[i].d], sk[i].maxd);
dp[1<<i][sk[i].e] = max(dp[1<<i][sk[i].e], sk[i].maxe);
dp[1<<i][sk[i].f] = max(dp[1<<i][sk[i].f], sk[i].maxf);
}
for(int state = 0; state < (1<<n); state++)
{
for(int i = 0; i < n; i++)
{
if(state & (1<<i))
{
for(int j = 1; j <= 6; j++)
{
if(sk[i].a == j && dp[state ^ (1<<i)][sk[i].f])
dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk[i].f] + sk[i].maxa);
if(sk[i].b == j && dp[state ^ (1<<i)][sk[i].d])
dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk[i].d] + sk[i].maxb);
if(sk[i].c == j && dp[state ^ (1<<i)][sk[i].e])
dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk[i].e] + sk[i].maxc);
if(sk[i].d == j && dp[state ^ (1<<i)][sk[i].b])
dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk[i].b] + sk[i].maxd);
if(sk[i].e == j && dp[state ^ (1<<i)][sk[i].c])
dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk[i].c] + sk[i].maxe);
if(sk[i].f == j && dp[state ^ (1<<i)][sk[i].a])
dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk[i].a] + sk[i].maxf);
}
}
}
}
for(int i = 1; i <= 6; i++)
maxx = max(maxx, dp[(1<<n) - 1][i]);
printf("%d\n", maxx);
}
return 0;
} |
|
收藏
淘帖
踩
