高手去散步

题意

给出一张无向带权图，可以从任意点出发、任意点结束，但同一个点不能重复经过。

要求求出能够走出的最大总路程。

思路

最直接的办法是从每个点出发做 DFS，枚举所有简单路径。

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#include <bits/stdc++.h>
using namespace std;

static vector<pair<int, int>> g[25];
static int vis[25];
static int ans = 0;

void dfs(int u, int dist) {
    ans = max(ans, dist);
    for (auto [v, w] : g[u]) {
        if (vis[v]) {
            continue;
        }
        vis[v] = 1;
        dfs(v, dist + w);
        vis[v] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    for (int i = 1; i <= n; ++i) {
        memset(vis, 0, sizeof(vis));
        vis[i] = 1;
        dfs(i, 0);
    }

    cout << ans << '\n';
    return 0;
}

brute.cpp 用访问标记数组直接回溯，适合小图对拍。

由于 $n <= 20$ ，这题更稳妥的正式做法是状态压缩 DP。把“已经走过哪些点”压成二进制集合 $mask$ ，设：

$dp[mask][u]$

表示当前已经访问过集合 $mask$ ，最后停在点 $u$ 时，能够得到的最大路径长度。

这张图展示样例图的结构：

graph G {
  1 -- 2 [label="10"];
  2 -- 3 [label="20"];
  3 -- 4 [label="30"];
  4 -- 1 [label="40"];
  1 -- 3 [label="50"];
  2 -- 4 [label="60"];
}

从图里可以看出，最长简单路径其实就是依次经过四个点并把三条较优边串起来。状态压缩 DP 正是在系统枚举“走过哪些点、最后停在哪”的所有可能。

初始时任意单点都能作为起点：

$dp[1<<u][u] = 0$

如果当前在 $u$ ，并且边 $(u, v, w)$ 存在，且 $v$ 还没访问过，那么：

$dp[mask | (1<<v)][v] = max(dp[mask | (1<<v)][v], dp[mask][u] + w)$

所有状态里的最大值就是答案。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;
const int MAXS = 1 << 20;

static int dp[MAXS][MAXN];
static vector<pair<int, int>> g[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < n; ++i) {
        dp[1 << i][i] = 0;
    }

    int ans = 0;
    int full = 1 << n;
    for (int mask = 1; mask < full; ++mask) {
        for (int u = 0; u < n; ++u) {
            if (dp[mask][u] == -1) {
                continue;
            }
            ans = max(ans, dp[mask][u]);
            for (auto [v, w] : g[u]) {
                if ((mask >> v) & 1) {
                    continue;
                }
                int nmask = mask | (1 << v);
                dp[nmask][v] = max(dp[nmask][v], dp[mask][u] + w);
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

状态数约为 $2^n * n$ ，每个状态沿邻边转移，总时间复杂度可以看成 $O(2^n * m)$ ，空间复杂度是 $O(2^n * n)$ 。

总结

这题的关键不是死搜，而是看出 $n <= 20$ 适合做状态压缩。把“已访问点集 + 当前终点”作为状态后，最长简单路径就能稳定求出来。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

代码

复杂度

总结

一图流解析