HDU 5418 – Victor and World [状态压缩DP]

点击打开HDU题目链接

题意

类似于可以重复走的旅行商问题,从起点1开始走编所有点,最后回到起点。

分析

因为节点不多,先用`floyd`求出最短路,然后用DP状态压缩求出来

官方题解

部分人可能对这道题的题面有点熟悉,其实这道题的标题本来叫做Victor and Around the World的,但是因为太长了所以就省略了两个单词。当然,这道题与POI 2014的那道Around the World其实没有任何关系。
我们首先需要预处理出任意两个国家之间的最短距离,因为数据范围很小,所以直接用Floyd就行了。之后,我们用`f[S][i]`表示访问国家的情况为S,当前最后访问的一个国家是i所需要的最小总油量,其中,S的二进制表示记录了访问国家的情况,S在二进制表示下的第i位(不管是从左往右还是从右往左都可以)如果是1则表示第i个国家被访问过了,否则表示第i个国家没有被访问过,那么`f[S|(1<<i)][i]=min(f[S][j]+f[i][j])`,其中i和j满足`S&(1<<j)=1`且`S&(1<<i)=0`。最开始时,除了`f[1][1]是0`,其他情况都是无穷大,之后先枚举S,再枚举i(我验题的时候因为这里搞反结果WA了),那么最终的答案就是`min(f[(1<<n)-1][i]+f[i][1])`

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

const int maxn = 20, inf = 0x3f3f3f3f;
int n, m, d[maxn][maxn], dp[1<<17][maxn];

void floyd() {
    for(int k = 1; k <= n; ++k)
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

void input() {
    scanf("%d%d", &n, &m);
    memset(d, inf, sizeof(d));
    for(int i = 1; i <= n; ++i)
        d[i][i] = 0;
    for (int i = 0; i < m; ++i) {
        int x, y, cost; scanf("%d%d%d", &x, &y, &cost);
        if(cost < d[x][y]) d[x][y] = d[y][x] = cost;
    }
}

int solve() {
    memset(dp, inf, sizeof(dp));
    dp[1][1] = 0;
    for(int i = 1; i < (1<<n); ++i) {
        for(int k = 1; k <= n; ++k) {
            if(!(i&(1<<(k-1)))) continue;
            for(int j = 1; j <= n; ++j) {
                if(i&(1<<(j-1))) continue;
                int to = i|(1<<(j-1));
                dp[to][j] = min(dp[to][j], dp[i][k] + d[k][j]);
            }
        }
    }
    int res = inf;
    for(int i = 2; i <= n; ++i)
        res = min(res, dp[(1<<n)-1][i] + d[i][1]);
    return res >= inf ? 0 : res;
}

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        input();
        floyd();
        printf("%d\n", solve());
    }
    return 0;
}

欢迎留言