思路：所求的哈密顿路径由三部分组成，一，所有节点的权值之和，二，每条边的权值之和，三，三元环的权值和。设集合S为拜访的点的集合，当向集合S中加入一个点，与上一条边的起点和终点有关。所以令dp[s][i][j]表示集合S通过边（i， j）加入j点之后的最大权值。
那么 dp[s][i][j] = max(dp[s][i][j], dp[p][k][i] + tmp). p表示未加入j点的集合，tmp表示加入j点之后增加的权值，tmp = v[j] + v[i] * v[j], 如果i, j, k三点构成三元环，那么tmp再加上v[i] * v[j] * v[k].
再用一个数组统计路径数。
注意答案会超过int，要用long long.
具体细节见代码
#include<cstdio> #include<set> #include<algorithm> #include<cstring> #include<iostream> #include<map> #include<queue> #include<vector> #include<stack> #include<string> #include<sstream> #include<set> #include<cmath> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 1e2 + 20; const double EPS = 1e-8; const int mod = 1e8; typedef unsigned long long ull; typedef long long LL; int dx[] = {0, 0, -1, 1, -1, -1, 1, 1}; int dy[] = {1, -1, 0, 0, -1, 1, -1, 1}; inline int dcmp(double x, double y){if(fabs(x - y) < EPS) return 0; return x > y ? 1 : -1; } int n, m; int g[13][13]; LL dp[1 << 13][13][13]; int num[1 << 13][13][13]; int v[13]; int main(){ int T; scanf("%d", &T); while(T--){ scanf("%d%d", &n, &m); for(int i = 0; i < n; ++i){ scanf("%d", &v[i]); } memset(g, 0, sizeof g); memset(num, 0, sizeof num); for(int i = 0; i < m; ++i){ int x, y; scanf("%d%d", &x, &y); g[x - 1][y - 1] = g[y - 1][x - 1] = 1; } memset(dp, -1, sizeof dp); for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ if(i == j) continue; if(g[i][j] == 0) continue; dp[1 << i | (1 << j)][i][j] = v[i] + v[j] + v[i] * v[j]; num[1 << i | (1 << j)][i][j] = 1; } } LL ans = -1; for(int i = 0; i < (1 << n); ++i){ for(int j = 0; j < n; ++j){ if(i & (1 << j)) continue; for(int k = 0; k < n; ++k){ if(j == k) continue; if(!(i & (1 << k)))continue; if(g[k][j] == 0) continue; for(int l = 0; l < n; ++l){ if(k == l)continue; if(l == j) continue; if(!(i & (1 << l)))continue; if(dp[i][l][k] == -1)continue; LL s = v[j] + v[k] * v[j] + dp[i][l][k]; if(g[j][l]) s += v[k] * v[j] * v[l]; if(dp[i | (1 << j)][k][j] < s){ dp[i | (1 << j)][k][j] = s; num[i | (1 << j)][k][j] = num[i][l][k]; } else if(dp[i | (1 << j)][k][j] == s){ num[i | (1 << j)][k][j] += num[i][l][k]; } } } } } LL cnt = 0; int t = (1 << n) - 1; for(int j = 0; j < n; ++j){ for(int k = 0; k < n; ++k){ if(j == k) continue; ans = max(ans, dp[t][j][k]); } } for(int j = 0; j < n; ++j){ for(int k = 0; k < n; ++k){ if(j == k) continue; if(dp[t][j][k] == ans) cnt += num[t][j][k]; } } cnt /= 2; if(n == 1) ans = v[0], cnt = 1; if(ans != -1) printf("%lld %lld\n", ans, cnt); else printf("0 0\n"); } } /* */
