經(jīng)典的TSP問題變種。狀態(tài)為f[i][j][k]，表示經(jīng)過二進(jìn)制數(shù)i所指的哈密頓路（第bi位為1表示經(jīng)過該點(diǎn)，為0表示不經(jīng)過該點(diǎn)），倒數(shù)第二個(gè)點(diǎn)為j，最后一個(gè)點(diǎn)為k。.value表示最大權(quán)值，.num表示能走出最大權(quán)值的路徑數(shù)。若圖中k到p有邊，f[i][j][k]則轉(zhuǎn)移到f[i'][k][p]。i' == i | (1 << p)。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-8-20 14:49:47
File Name: pku2288.cpp
Description:
************************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout<<#x<<": "<<x<<endl)
const int maxint=0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template<class T>void show(T a, int n)
{for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
typedef struct state_t
{
int64 value, num;
};
int n, m;
int64 c[13];
int g[13][13];
state_t f[1 << 13][13][13];
void dp(int64 &ans_value, int64 &ans_num)
{
if (n == 1)
{
ans_value = c[0];
ans_num = 2;
return;
}
memset(f, 0, sizeof(f));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) if (g[i][j] != 0)
{
f[(1 << i) | (1 << j)][i][j].value = c[i] + c[j] + c[i] * c[j];
f[(1 << i) | (1 << j)][i][j].num = 1;
}
for (int i = 0; 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) if (f[i][j][k].value != 0)
{
for (int p = 0; p < n; p++) if (((i >> p) & 1) == 0 && g[k][p] != 0)
{
int64 t = c[p] + c[p] * c[k];
if (g[j][p] != 0) t += c[j] * c[k] * c[p];
if (f[i][j][k].value + t > f[i | (1 << p)][k][p].value)
{
f[i | (1 << p)][k][p].value = f[i][j][k].value + t;
f[i | (1 << p)][k][p].num = f[i][j][k].num;
}
else if (f[i][j][k].value + t == f[i | (1 << p)][k][p].value)
f[i | (1 << p)][k][p].num += f[i][j][k].num;
}
}
}
ans_value = 0;
ans_num = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (f[(1 << n) - 1][i][j].value > ans_value)
{
ans_value = f[(1 << n) - 1][i][j].value;
ans_num = f[(1 << n) - 1][i][j].num;
}
else if (f[(1 << n) - 1][i][j].value == ans_value)
ans_num += f[(1 << n) - 1][i][j].num;
}
int main()
{
int ca;
for (scanf("%d", &ca); ca--;)
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%lld", &c[i]);
memset(g, 0, sizeof(g));
for (int i = 0; i < m; i++)
{
int t1, t2;
scanf("%d%d", &t1, &t2);
t1--;
t2--;
g[t1][t2] = g[t2][t1] = 1;
}
int64 ans1, ans2;
dp(ans1, ans2);
cout << ans1 << " " << ans2 / 2 << endl;
}
return 0;
}