思路：总共有18条边，9个三角形。
极大极小化搜索+剪枝比较慢，所以用记忆化搜索！！
用state存放当前的加边后的状态，并判断是否构成三角形，找出最优解。
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define inf 1<<25
using namespace std;
int edge[][]={{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,}
,{,},{,},{,}};
int tri[][]={{,,},{,,},{,,},{,,},{,,},{,,},{,,},{,,},{,,}};
int p[],dp[<<];
int cal(int state,int e)
{
int ans=;
for(int i=;i<;i++){
bool flag=;
for(int j=;j<;j++) //判断边e是否在这个三角形中
if(e==tri[i][j]) flag=true;
if(flag){ //e在这个三角形中
for(int j=;j<;j++){
if(!(p[tri[i][j]]&state||e==tri[i][j])){ //如果满足条件说明tri[i][j]这条边不存在且e也不是这条边
ans--;break; //也就是不能构成三角形，否则能构成
}
}
ans++;
}
}
return ans;
}
int dfs(int state)
{
if(dp[state]!=-inf) return dp[state];
int ans=-inf;
for(int i=;i<;i++){
if(!(state&p[i])){
int tt=cal(state,i);
if(tt) tt+=dfs(state|p[i]);
else tt-=dfs(state|p[i]);
ans=max(ans,tt);
}
}
return dp[state]=ans;
}
int main()
{
//freopen("1.txt","r",stdin);
int t,u,v,ca=,m;
p[]=;
for(int i=;i<;i++) p[i]=p[i-]*;
for(int i=;i<(<<);i++) dp[i]=-inf;
dp[(<<)-]=;
scanf("%d",&t);
while(t--){
scanf("%d",&m);
int m0=,m1=,tt=,state=,side=;
while(m--){
scanf("%d%d",&u,&v);
for(int i=;i<;i++)
if(edge[i][]==u&&edge[i][]==v){
tt=cal(state,i);
state|=p[i];
side==?m0+=tt:m1+=tt;
side++;
if(tt) side++;
side%=;
break;
}
}
int ans=m0-m1;
if(side==) ans+=dfs(state);
else ans-=dfs(state);
printf("Game %d: %s\n",++ca,ans>?"A wins.":"B wins.");
}
return ;
}