做题感悟：这题虽然看似很简单其实如果细心的话也不难，但是wa 了 n 次，wa 在了统计最优解个数上，开始没有开数组然后最后统计达到目标状态最优解的个数，这样是不对的，因为你只记录了最终的状态，可能在形成最优解的过程中有许多方法构成了最优解。
解题思路：
(1) 、这题很容易想到状态方程 ： dp[ S ^ (1<<k) ] [ j ] [ k ] = max(dp[ S ^ (1<<k) ] [ j ] [ k ] , dp[ S ] [ i ] [ j ] + Wk ) ; dp[ S ^ (1<<k) ] [ j ] [ k ] 代表达到状态S ^ (1<<k) 并以 j , k 结尾的路径最优解
；
(2)、还要有记录路径的数组，因为有可能一种状态有许多方法构成 ，注意用 long long or __int64 ;
(3)、注意只有一个点的情况。
代码：
#include<iostream>
#include<ctime>
#include<fstream>
#include<sstream>
#include<stack>
#include<cstring>
#include<map>
#include<vector>
#include<cstdio>
#include<algorithm>
#define INT __int64
using namespace std ;
const int INF = 9999999 ;
const INT MY = 10 + 10 ;
const INT MX = (1<<13) + 10 ;
INT n ,m ;
INT dp[MX][MY][MY] ,v[MY] ,w[MY][MY] ,num[MX][MY][MY] ;
void DP()
{
for(INT S = 0 ;S < (1<<n) ;S++)
for(INT i = 0 ;i < n ;i++)
for(INT j = 0 ;j < n ;j++)
if(dp[S][i][j] != -1)
{
for(INT k = 0 ;k < n ;k++)
{
if(k == i || k == j || S & (1<<k) || !w[j][k]) continue ;
INT mx = v[k] + v[j]*v[k] + dp[S][i][j] ;
if(w[i][k]) mx += v[i]*v[j]*v[k] ;
INT& best = dp[S^(1<<k)][j][k] ;
if(best < mx)
{
best = mx ;
num[S^(1<<k)][j][k] = num[S][i][j] ;
}
else if(best == mx)
num[S^(1<<k)][j][k] += num[S][i][j] ;
}
}
INT sum = 0 ,ans = -1 ;
for(INT i = 0 ;i < n ;i++)
for(INT j = 0 ;j < n ;j++)
{
if(dp[(1<<n)-1][i][j] == -1) continue ;
if(dp[(1<<n)-1][i][j] > ans)
{
ans = dp[(1<<n)-1][i][j] ;
sum = num[(1<<n)-1][i][j] ;
}
else if(dp[(1<<n)-1][i][j] == ans)
sum += num[(1<<n)-1][i][j] ;
}
if(sum)
cout<<ans<<" "<<sum/2<<endl ;
else cout<<"0 0"<<endl ;
}
int main()
{
INT Tx ;
scanf("%I64d",&Tx) ;
while(Tx--)
{
scanf("%I64d%I64d",&n,&m) ;
for(INT i = 0 ;i < n ;i++)
scanf("%I64d",&v[i]) ;
memset(w ,0 ,sizeof(w)) ;
memset(dp ,-1 ,sizeof(dp)) ;
memset(num ,0 ,sizeof(num)) ;
for(INT i = 0 ;i < m ;i++)
{
INT x ,y ;
scanf("%I64d%I64d",&x ,&y) ;
x-- ; y-- ;
w[x][y] = w[y][x] = 1 ;
INT S = (1<<x) + (1<<y) ;//初始化两个点
dp[S][x][y] = dp[S][y][x] = v[x] + v[y] + v[x]*v[y] ;
num[S][x][y] = 1 ;
num[S][y][x] = 1 ;
}
if(n == 1) //特殊处理
{
cout<<v[0]<<" "<<1<<endl ;
continue ;
}
DP() ;
}
return 0 ;
}