哈密顿路径稍微修改了一下,需要记录最后两个位置。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
using namespace std;
const int N=13;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int f[1<<N][N][N],n,m,v[N];bool mp[N][N];ll c[1<<N][N][N];
int main()
{
    int T;qr(T);
    while(T--)
    {
        qr(n),qr(m);memset(mp,0,sizeof(mp));
        for(int i=0;i<n;i++)qr(v[i]);memset(f,0xcf,sizeof(f));
        for(int i=1,x,y;i<=m;i++)
        {
            qr(x),qr(y),--x,--y;
            mp[x][y]=mp[y][x]=1;
            f[(1<<x)+(1<<y)][x][y]=f[(1<<x)+(1<<y)][y][x]=v[x]+v[y]+v[x]*v[y];
            c[(1<<x)+(1<<y)][x][y]=c[(1<<x)+(1<<y)][y][x]=1;
        }
        if(n==1){qw(v[0]),putchar(' '),puts("1");continue;}
        for(int i=1;i<1<<n;i++)
            for(int j=0;j<n;j++)if(i>>j&1)
                for(int k=0;k<n;k++)if((i>>k&1)&&(j!=k)&&f[i][j][k]!=0xcfcfcfcf)
                    for(int l=0;l<n;l++)if((k!=l)&&!(i>>l&1)&&mp[k][l])
                    {
                        int tmp=f[i][j][k]+v[k]*v[l]+v[l],sz=c[i][j][k];
                        if(mp[j][l])
                            tmp+=v[j]*v[k]*v[l];//成环
                        if(tmp>f[i|(1<<l)][k][l])f[i|(1<<l)][k][l]=tmp,c[i|(1<<l)][k][l]=sz;
                        else if(tmp==f[i|(1<<l)][k][l])c[i+(1<<l)][k][l]+=sz;
                    }
 
        int all=(1<<n)-1,ans=0;ll anc=0;
        for(int j=0;j<n;j++)
            for(int k=0;k<n;k++)if(j!=k)
            {
                if(f[all][j][k]>ans)ans=f[all][j][k],anc=c[all][j][k];
                else if(f[all][j][k]==ans)anc+=c[all][j][k];
            }
        qw(ans),putchar(' '),qw(anc>>1);puts("");
    }
    return 0;
}
/*
1
3 1
2 4 3
1 3
27 0
*/