Solutions CS101

Appearance

T30201: 旅行售货商问题 ​

bitmask dp, http://cs101.openjudge.cn/practice/30201/

思路：以前没接触过状压DP, 看懂课件上的做法后, 自己码了一遍, 嵌套层数有点多, 难点是理清思路 (下次记得还是不要随便命名变量了, 不然自己都看不懂)

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

// Bitmask DP solution for the Traveling Salesman Problem (TSP)
int main() {
    int n;
    cin >> n;
    vector<vector<int>> grid(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }

    int total = 1 << n;
    const int INF = 1e9;
    vector<vector<int>> dp(total, vector<int>(n, INF));
    dp[1][0] = 0;
    for (int mask = 1; mask < total; mask += 2) {
        for (int j = 0; j < n; j++) {
            if (dp[mask][j] != INF) {
                for (int u = 1; u < n; u++) {
                    if (((mask >> u) & 1) == 0) {
                        int nxt = mask | (1 << u);
                        dp[nxt][u] = min(dp[nxt][u], dp[mask][j] + grid[j][u]);
                    }
                }
            }
        }
    }

    int ans = INF;
    for (int i = 1; i < n; i++) {
        ans = min(ans, dp[total - 1][i] + grid[i][0]);
    }
    cout << ans << endl;
    return 0;
}

用时50min

cpp
#include <iostream>
#include <vector>
using namespace std;

constexpr static int INF = 1e9;

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    cin >> n;
    vector<vector<int>> G(n, vector<int>(n));
    for (auto &g : G)
        for (auto &x : g)
            cin >> x;

    int N = 1 << n;
    vector<vector<int>> dp(N, vector<int>(n + 1, INF));
    dp[1][0] = 0;

    for (int mask = 1; mask < N; ++mask)
        for (int u = 0; u < n; ++u)
        {
            if (!(mask & (1 << u)))
                continue;
            if (dp[mask][u] == INF)
                continue;
            for (int v = 0; v < n; ++v)
            {
                if ((mask & (1 << v)))
                    continue;
                dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + G[u][v]);
            }
        }

    int ans = INF;
    for (int i = 1; i < n; ++i)
        ans = min(ans, dp[N - 1][i] + G[i][0]);
    cout << ans << '\n';
    return 0;
}

共用时1h

思路：状压dp,自底向上写动态规划，动态规划的难点在于知道dp数组记录的是什么，这里记录在到达不同点的状态下（用二进制记录，即为状压），到达最后一个城市所用的最大值，直到把所有城市都遍历过，1<<k-1状态，再加上所有结束点回到起点，计算最大值。

ps：如果不用回到原点，可以这么写,dp数组的含义仍然不变，最后只要找dp[1<<k-1]中的最小值。

cpp
for(int i = 0; i < n; i++)
    dp[1<<i][i] = 0;

代码：

cpp
#include<iostream>
#include<vector>
using namespace std;
int min(int a,int b){
    return (a<b)?a:b;
}
int main()
{
    int n;
    cin>>n;
    vector<vector<int>> cost(n,vector<int>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>cost[i][j];
        }
    }
    int mask[1<<18];//状压dp：把每个城市去没去过的状态记录一下
    vector<vector<int>> dp(1<<18,vector<int>(n,1000000000));
    dp[1][0]=0;//一开始什么都不走的时候花费为0
    //由于最后的路线是一个圈，所以我们不妨假定就从下标为0的城市出发，上面的dp数组是（状态，最后在的城市）所花的最小值。
    for(int i=1;i<(1<<n);i+=2){
        for(int j=0;j<n;j++)//自底向上的dp写法。
        {
            int curr_dist=dp[i][j];
            if(dp[i][j]==1000000000){
                continue;
            }
            for(int k=0;k<n;k++){
                if((i>>k)&1){
                    continue;
                }
                int new_i=i|(1<<k);
                int new_cost=cost[j][k];
                dp[new_i][k]=min(dp[new_i][k],new_cost+dp[i][j]);
            }
        }   
    }
    int ans=1000000000;
    for(int i=1;i<n;i++){
        ans=min(ans,cost[0][i]+dp[(1<<n)-1][i]);
    }
    cout<<ans;
    return 0;
}

思路：即寻找有向图的最小哈密顿环．令 fu,S (u∈[n], S∈2[n]∖{1,u}) 为自 1 至 u、途径点集 S 的最小路径长度，有 fu,∅=w(1,u) 和 fu,S=minv∈S{fv,S∖{v}+w(v,u)} (S≠∅)，答案为 f1,[n]∖{1}．时间复杂度为 O(2nn2)．

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

void tomin(auto& x, const auto& y) {
    if(x > y) x = y;
}
const int N = 18;
int G[N][N];
int f[1 << N][N];
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) cin >> G[i][j];
    for(int u = 1; u < n; u++) f[0u][u] = G[0][u];
    for(unsigned S = 2u; S < (1u << n); S += 2u) {
        for(int u = 0; u < n; u++) {
            if(S & (1u << u)) continue;
            f[S][u] = numeric_limits<int>::max();
            for(int v = 0; v < n; v++)
                if(S & (1u << v))
                    tomin(f[S][u], f[S & ~(1u << v)][v] + G[v][u]);
        }
    }
    cout << f[(1u << n) - 2u][0];
    return 0;
}