高手去散步(Master Goes for a Walk) 题解

思路分析

由于 $n \le 20$，枚举每一个观景点作为起点进行深度优先搜索（DFS），用 vis[] 标记已走过的观景点以防重复经过，回溯时恢复现场，维护所有合法简单路径长度的最大值即可（也可用状压 DP dp[mask][u] 在 $O(2^n m)$ 内求解）。注意图可能不连通，必须尝试所有点作为起点。

参考代码

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

vector<pair<int, int>> adj[21];
int dp[1 << 20][20];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 0; i < m; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    int full = 1 << n;
    for (int mask = 0; mask < full; ++mask)
        for (int u = 0; u < n; ++u)
            dp[mask][u] = -1;
    for (int u = 0; u < n; ++u)
        dp[1 << u][u] = 0;

    int ans = 0;
    for (int mask = 1; mask < full; ++mask)
    {
        for (int u = 0; u < n; ++u)
        {
            int cur = dp[mask][u];
            if (cur < 0) continue;
            if (cur > ans) ans = cur;
            for (const auto& e : adj[u])
            {
                int v = e.first, w = e.second;
                if (!(mask & (1 << v)))
                {
                    int nmask = mask | (1 << v);
                    if (cur + w > dp[nmask][v])
                        dp[nmask][v] = cur + w;
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}