11.23-周日上午-状态压缩专题测试

yingxi · 2025-11-30 10:18:23 · 个人记录

P4802 [CCO 2015] 路短最

他不想重复访问任何城市，请帮他找出最长路径。

2\le n \le 18

那么我们可以想到Hamilton路径，原题面是让我们从 0 到 n-1 不重不漏地经过每个点恰好一次。题目又保证了有一条从城市 0 到 n-1 的路径。所以这道题就是给我们 m 条边，去跑一个Hamilton通路。但是这道题不一定要所有点都经过，只是要最长。

设 dp[st][i] 表示目前状态 st（第 i 位为 1 就走过，否则没走过），而目前走到了 i。那么答案就是 dp[st][n - 1]。其中 st 是所有可能的状态。

推一下状转：我们先枚举每一种状态，再枚举每一位为 1 的，然后把这一位在 st 中去掉，得到上一次（去 j 之前）的状态。然后枚举 k，表示 j 是从 k 来的，然后状转就是：dp[st][j] = min(dp[st][j], dp[st ^ (1 << j)][k] + dis[k][j])。也就是在原来的自己和从 k 过来之中二选一。

注意是从 0 开始的，所以 dp[1][0] 要赋值为 0。然后其他的就是极大值。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 25;
int n, dis[N][N], dp[1 << 20][N];
int m;
signed main() 
{
    cin >> n >> m;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            dis[i][j] = -1e9;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        dis[u][v] = w;
    }
    int maxi = (1 << n) - 1;
    for (int st = 0; st <= maxi; st++)
        for (int j = 0; j < n; j++)
            dp[st][j] = -1e9;
    dp[1][0] = 0;
    for (int i = 0; i <= maxi; i++) 
    {
        for (int j = 0; j < n; j++) 
        {
            if (!((i >> j) & 1))
                continue;
            int tmp = (i ^ (1 << j));
            for (int k = 0; k < n; k++)
                if ((tmp >> k) & 1)
                    dp[i][j] = max(dp[i][j], dp[tmp][k] + dis[k][j]);
        }
    }
    int ans = 0;
    for (int i = 0; i <= maxi; i++)
        ans = max(ans, dp[i][n - 1]);
    cout << ans;
    return 0;
}