最佳三角形哈密顿路径问题题解

一、题目分析

题目要求找到一条哈密顿路径，使其价值最大化。路径价值由三部分组成：

1. 所有岛屿价值之和；
2. 相邻岛屿价值乘积之和；
3. 连续三个岛屿构成三角形时，三个岛屿价值的乘积之和。

关键点：

• 状态压缩动态规划（DP）处理哈密顿路径；
• 逆序路径视为同一条路径，最终结果需除以2。

二、算法思路

1. 状态定义：

   • dp[mask][i][j]：当前已访问节点集合为mask，路径最后两个节点为i和j的最大价值；
   • num[mask][i][j]：对应状态的路径数量。

2. 状态转移：

   • 枚举所有可能的路径扩展，检查是否形成三角形并更新价值；
   • 利用位运算高效处理节点集合。

3. 初始化：

   • 每个节点单独作为起点，初始价值为节点自身价值。

4. 结果统计：

   • 遍历所有可能的哈密顿路径，取最大值并统计数量，注意逆序路径需去重。

三、代码实现

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long LL;
LL n, m, val[14], dp[1 << 13][14][14], num[1 << 13][14][14];
bool map[14][14]; // 邻接矩阵

bool ok(int i, int j) { // 判断节点j是否在集合i中
    if (j == 0) return true;
    return i & (1 << (j - 1));
}

void init() {
    memset(dp, -1, sizeof(dp));
    memset(map, false, sizeof(map));
    memset(num, 0, sizeof(num));
}

int main() {
    int ncase;
    cin >> ncase;
    while (ncase--) {
        init();
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; ++i)
            scanf("%d", val + i);
        for (int i = 1; i <= m; ++i) {
            int a, b;
            scanf("%d %d", &a, &b);
            map[a][b] = map[b][a] = true;
        }
        
        if (n == 1) { // 特殊情况处理
            cout << val[1] << " " << 1 << endl;
            continue;
        }
        
        // 初始化每个节点作为起点
        for (int i = 1; i <= n; ++i) {
            int mask = 1 << (i - 1);
            dp[mask][i][0] = val[i];
            num[mask][i][0] = 1;
        }
        
        // 状态转移
        for (int mask = 0; mask < (1 << n); ++mask) {
            for (int j = 1; j <= n; ++j) { // 即将加入的节点
                if (!ok(mask, j)) continue;
                int prev_mask = mask ^ (1 << (j - 1));
                
                for (int k = 1; k <= n; ++k) { // 前一个节点
                    if (k == j || !ok(mask, k) || !map[k][j]) continue;
                    
                    for (int q = 0; q <= n; ++q) { // 前前一个节点
                        if (q == k || q == j || (q && !map[q][k]) || !ok(prev_mask, q)) continue;
                        if (dp[prev_mask][k][q] == -1) continue;
                        
                        int new_val = val[j] + val[j] * val[k] + dp[prev_mask][k][q];
                        if (q && map[q][j]) // 形成三角形
                            new_val += val[q] * val[k] * val[j];
                            
                        if (new_val == dp[mask][j][k])
                            num[mask][j][k] += num[prev_mask][k][q];
                        else if (new_val > dp[mask][j][k]) {
                            dp[mask][j][k] = new_val;
                            num[mask][j][k] = num[prev_mask][k][q];
                        }
                    }
                }
            }
        }
        
        // 结果统计
        LL max_val = -1, count = 0;
        int full_mask = (1 << n) - 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                if (dp[full_mask][i][j] > max_val) {
                    max_val = dp[full_mask][i][j];
                    count = num[full_mask][i][j];
                } else if (dp[full_mask][i][j] == max_val) {
                    count += num[full_mask][i][j];
                }
            }
        }
        
        if (max_val == -1)
            printf("0 0\n");
        else
            cout << max_val << " " << count / 2 << endl; // 逆序路径去重
    }
    return 0;
}

四、代码解释

1. 状态压缩：

   • 使用mask（整数）表示已访问节点集合，每一位对应一个节点；
   • dp[mask][i][j]记录路径末尾两个节点为i和j的最大价值。

2. 状态转移：

   • 遍历所有可能的路径扩展，检查是否存在边和三角形；
   • 更新价值时考虑节点自身价值、相邻乘积及三角形乘积。

3. 结果处理：

   • 遍历所有哈密顿路径状态，取最大值并统计数量；
   • 由于逆序路径视为同一条，最终数量需除以2。

五、示例解析

输入样例1：

3 3  
2 2 2  
1 2  
2 3  
3 1  

1. 初始化：

   • 每个节点单独作为起点，价值为2。

2. 状态转移：

   • 扩展路径时，每条边贡献2×2=4；
   • 每个三角形贡献2×2×2=8；
   • 所有哈密顿路径价值为22（如1→2→3：2+2+2 +4+4 +8=22）。

3. 结果：

   • 最大价值22，路径数量3（去重后）。

六、复杂度分析

• 时间复杂度：O(n² × 2ⁿ)，状态数为O(2ⁿ × n²)，每次转移需O(n)；
• 空间复杂度：O(2ⁿ × n²)，存储DP状态。

七、关键技巧

1. 状态压缩DP：高效处理哈密顿路径问题；
2. 路径末尾双节点记录：精确计算三角形贡献；
3. 逆序路径去重：结果数量除以2消除对称性。