现有n  个零件，小Y花费了很多时间来收集它们，现在他想把零件拼在一起，拼完就可以召唤神龙了。已知零件之间存在相邻的关系，拥有相邻关系的零件在最终的组装结果中就是相邻的，并且组装过程中每次只能通过相邻关系来组合零件。小Y每次可以选择两个零件（也可以是两个零件块，或一个零件与一个零件块）拼起来，成为一个零件块，但要求拼接时必须在两个零件块（或零件）之间存在相邻的零件。除此之外这些零件两两之间有类似于磁力的排斥关系，当将两个零件或者零件块拼接在一起的时候，会受到两边的零件间的排斥力，排斥力的大小=两边零件的相互排斥对数*单侧零件个数的最大值（拼接完成的零件组合体中的零件之间排斥不计）。现在已知零件间的相邻关系和排斥关系，小Y自然想知道如何拼接不费力，因此需要求出将这些零件组装起来的最优方案，使得所有步骤的排斥力之和最小。

#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <bitset>#include <map>#include <queue>#include <stack>#include <vector>#include <cassert>#include <ctime>#define rep(i,m,n) for(i=m;i<=(int)n;i++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define sys system("pause")#define ls rt<<1#define rs rt<<1|1const int maxn=1e5+10;const int N=5e2+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q,ll mo){ll f=1;while(q){if(q&1)f=f*p%mo;p=p*p%mo;q>>=1;}return f;}int n,m,k,t,a[15][15],b[15][15],dp[1<<14],num[1<<14],cnt1[1<<14],cnt2[1<<14];void upd(int &x,int y){if(x>y)x=y;}void init(){    for(int i=1;i<(1<<n);i++)    {        num[i]=1+num[i-(i&(-i))];    }    for(int i=1;i<(1<<n);i++)    {        cnt1[i]=cnt2[i]=0;        for(int j=0;j<n;j++)        {            for(int k=j+1;k<n;k++)            {                if((i>>j&1)&&(i>>k&1))                {                    cnt1[i]+=a[j][k];                    cnt2[i]+=b[j][k];                }            }        }    }}int main(){    int i,j;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        rep(i,0,n-1)rep(j,0,n-1)scanf("%d",&a[i][j]);        rep(i,0,n-1)rep(j,0,n-1)scanf("%d",&b[i][j]);        init();        rep(i,0,(1<<n)-1)dp[i]=inf;        rep(i,0,n-1)dp[1<<i]=0;        dp[0]=0;        rep(i,1,(1<<n)-1)        {            for(j=((i-1)&i);j;j=((j-1)&i))            {                int sx=j,sy=i-j;                int num1=cnt1[i]-cnt1[sx]-cnt1[sy],num2=cnt2[i]-cnt2[sx]-cnt2[sy];                if(num1)upd(dp[i],dp[sx]+dp[sy]+num2*max(num[sx],num[sy]));            }        }        printf("%d\n",dp[(1<<n)-1]);    }    return 0;}