分成两问。第一问求Hamilton路径最大赋值，第二问求值最大的hamilton路径有多少个。使用状态压缩来记录状态简化转移。
把细节关注好是重点。本题代码比较繁琐，一定要养成良好的代码习惯，避免出现奇怪的bug。
第一份代码，用bfs实现记忆化搜索。
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
const int N = 14;
const int INF = 0x3f3f3f3f3f3f3f3f;
int T, n, m, val[N], res[N][N][1 << N], cnt[N][N][1 << N];
bool G[N][N];
void Init () {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
G[i][j] = 0;
for (int k = 0; k < (1 << N); ++k) {
res[i][j][k] = -INF;
cnt[i][j][k] = 0;
}
}
}
}
struct Node {
int cur, pre, sit;
};
queue <Node> que;
signed main () {
// freopen ("data.in", "r", stdin);
cin >> T;
while (T--) {
Init ();
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> val[i];
}
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
G[u][v] = G[v][u] = true;
}
if (n == 1) {
cout << val[1] << " 1" << endl;
continue;
}
for (int i = 1; i <= n; ++i) {
res[i][0][1 << (i - 1)] = 0;
cnt[i][0][1 << (i - 1)] = 1;
que.push ((Node) {i, 0, 1 << (i - 1)});
}
while (!que.empty ()) {
Node _node = que.front ();
que.pop ();
// printf ("Node now: {cur = %d, pre = %d, sit = %d, res = %d}
", _node.cur, _node.pre, _node.sit, res[_node.cur][_node.pre][_node.sit]);
for (int i = 1; i <= n; ++i) {
if (G[_node.cur][i] == false) {
continue;
}
if ((_node.sit & (1 << (i - 1))) == 0) {
// printf ("%d : yes!
", i);
// 第二位尚未到达
int _newres = res[_node.cur][_node.pre][_node.sit] + val[_node.cur] * val[i];
if (G[i][_node.pre]) {
_newres += val[_node.pre] * val[_node.cur] * val[i];
}
int _newcur = i;
int _newpre = _node.cur;
int _newsit = _node.sit | (1 << (i - 1));
// printf ("Node next: {cur = %d, pre = %d, sit = %d, res = %d}
", _newcur, _newpre, _newsit, _newres);
if (_newres > res[_newcur][_newpre][_newsit]) {
cnt[_newcur][_newpre][_newsit] = cnt[_node.cur][_node.pre][_node.sit];
// printf ("cnt next = %d
", cnt[_newcur][_newpre][_newsit]);
if (res[_newcur][_newpre][_newsit] < 0) {
que.push ((Node) {_newcur, _newpre, _newsit});
}
res[_newcur][_newpre][_newsit] = _newres;
} else if (_newres == res[_newcur][_newpre][_newsit]) {
// printf ("cnt next += %d
", cnt[_node.cur][_node.pre][_node.sit]);
cnt[_newcur][_newpre][_newsit] += cnt[_node.cur][_node.pre][_node.sit];
}
}
}
}
int ans1 = -INF, ans2 = 0, sum = 0;
for (int i = 1; i <= n; ++i) {
sum += val[i];
for (int j = 1; j <= n; ++j) {
if (ans1 < res[i][j][(1 << n) - 1]) {
ans1 = res[i][j][(1 << n) - 1];
ans2 = cnt[i][j][(1 << n) - 1];
} else if (ans1 == res[i][j][(1 << n) - 1]) {
ans2 += cnt[i][j][(1 << n) - 1];
}
// cout << ans2 << endl;
}
}
if (ans1 < 0) {
cout << "0 0" << endl;
} else {
cout << ans1 + sum << " " << ans2 / 2 << endl;
}
}
}
第二份代码，使用循环的形式。
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int N = 14;
const int INF = 0x3f3f3f3f3f3f3f3f;
int T, n, m, val[N], res[N][N][1 << N], cnt[N][N][1 << N];
bool G[N][N];
void Init () {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
G[i][j] = false;
for (int k = 0; k < (1 << N); ++k) {
res[i][j][k] = -INF;
cnt[i][j][k] = 0;
}
}
}
}
signed main () {
cin >> T;
while (T--) {
Init ();
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> val[i];
}
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
G[u][v] = G[v][u] = true;
}
if (n == 1) {
cout << val[1] << " 1" << endl;
continue;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == j || !G[i][j]) {
continue;
}
int s1 = 1 << (i - 1);
int s2 = 1 << (j - 1);
res[i][j][s1 ^ s2] = val[i] * val[j];
cnt[i][j][s1 ^ s2] = 1;
}
}
for (int sit = 0; sit < 1 << n; ++sit) {
for (int u = 1; u <= n; ++u) {
int s1 = 1 << (u - 1);
if (!sit & s1) continue;
for (int v = 1; v <= n; ++v) {
int s2 = 1 << (v - 1);
if (u == v || (!G[u][v]) || (!(sit & s2)) || res[v][u][sit] == -INF) continue;
for (int t = 1; t <= n; ++t) {
int s3 = 1 << (t - 1);
if (t == u || t == v || (sit & s3) || !G[v][t]) continue;
int sum = val[v] * val[t];
if (G[u][t]) {
sum += val[u] * val[v] * val[t];
}
if (res[v][u][sit] + sum > res[t][v][sit ^ s3]) {
res[t][v][sit ^ s3] = res[v][u][sit] + sum;
cnt[t][v][sit ^ s3] = cnt[v][u][sit];
} else if (res[v][u][sit] + sum == res[t][v][sit ^ s3]) {
cnt[t][v][sit ^ s3] += cnt[v][u][sit];
}
}
}
}
}
int ans1 = -INF, ans2 = 0, sum = 0;;
for (int i = 1; i <= n; ++i) {
sum += val[i];
for (int j = 1; j <= n; ++j) {
if (ans1 < res[i][j][(1 << n) - 1]) {
ans1 = res[i][j][(1 << n) - 1];
ans2 = cnt[i][j][(1 << n) - 1];
} else if (ans1 == res[i][j][(1 << n) - 1]) {
ans2 += cnt[i][j][(1 << n) - 1];
}
}
}
if (ans1 < 0) {
cout << "0 0" << endl;
} else {
cout << ans1 + sum << " " << ans2 / 2 << endl;
}
}
}