文字教学

这道题是求无向图的最长路径（不重复经过节点），因为节点数 $n \le 20$，可以用状态压缩DP解决：

1. 状态定义：用 dp[mask][u] 表示“已走过的节点集合为 mask（二进制第 $i$ 位为1表示节点 $i+1$ 已走过），最后一个节点是 $u$”时的最长路径长度。
2. 状态转移：对于每个状态 (mask, u)，遍历 $u$ 的所有邻居 $v$，若 $v$ 未在 mask 中，则转移到新状态 (mask | (1<<(v-1)), v)，长度加上 $u$ 到 $v$ 的边权。
3. 初始化：每个节点单独作为起点时，mask 只有该节点，路径长度为0。
4. 结果：遍历所有状态的 dp 值，取最大值即为最长路径。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 21;
int g[N][N], dp[1<<20][N];

int main() {
    int n, m, u, v, w, ans = 0;
    cin >> n >> m;
    memset(g, -1, sizeof(g));
    memset(dp, -1, sizeof(dp));
    
    for (int i = 0; i < m; ++i) {
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = w;
    }
    
    for (int i = 1; i <= n; ++i)
        dp[1<<(i-1)][i] = 0;
    
    for (int mask = 1; mask < (1<<n); ++mask) {
        for (int u = 1; u <= n; ++u) {
            if (!(mask & (1<<(u-1))) || dp[mask][u] == -1) continue;
            for (int v = 1; v <= n; ++v) {
                if (mask & (1<<(v-1)) || g[u][v] == -1) continue;
                int nm = mask | (1<<(v-1));
                dp[nm][v] = max(dp[nm][v], dp[mask][u] + g[u][v]);
            }
        }
    }
    
    for (int mask = 1; mask < (1<<n); ++mask)
        for (int u = 1; u <= n; ++u)
            ans = max(ans, dp[mask][u]);
    
    cout << ans << endl;
    return 0;
}