专栏文章

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

yyingxi
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimxugym
此快照首次捕获于
2025/12/01 17:19
3 个月前
此快照最后确认于
2025/12/01 17:19
3 个月前
查看原文

P4802 [CCO 2015] 路短最

他不想重复访问任何城市，请帮他找出最长路径。
2≤n≤182\le n \le 18
那么我们可以想到Hamilton路径，原题面是让我们从 00 到 n−1n-1 不重不漏地经过每个点恰好一次。题目又保证了有一条从城市 00 到 n−1n-1 的路径。所以这道题就是给我们 mm 条边，去跑一个Hamilton通路。但是这道题不一定要所有点都经过，只是要最长。
设 dp[st][i]dp[st][i] 表示目前状态 stst（第 ii 位为 11 就走过，否则没走过），而目前走到了 ii。那么答案就是 dp[st][n−1]dp[st][n - 1]。其中 stst 是所有可能的状态。
推一下状转：我们先枚举每一种状态，再枚举每一位为 11 的，然后把这一位在 stst 中去掉，得到上一次（去 jj 之前）的状态。然后枚举 kk，表示 jj 是从 kk 来的，然后状转就是：dp[st][j]=min(dp[st][j],dp[stdp[st][j] = min(dp[st][j], dp[st ^ (1<<j)][k]+dis[k][j])(1 << j)][k] + dis[k][j])。也就是在原来的自己和从 kk 过来之中二选一。
注意是从 00 开始的，所以 dp[1][0]dp[1][0] 要赋值为 00。然后其他的就是极大值。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...