daimayuan249 | 旅行商(状压, dp, 剪枝)

IhopeIdieyoung / 2023-08-19 / 原文

不难写出转移方程, \(f_{i, j}\)表示此时所走过的状态pattern为i, 目前所在城市为j. 则转移方程为:

\[f_{i, j} = min\{f_{i, j}, f_{i - 2^k, k} + a_{k, j}\} \]

k为合法的前继城市, 则\(i - 2^k\)就是合法的前继状态(当然这题写push型转移也可以, wls就写的push型转移)

最后可以看情况进行剪枝(状压枚举和dfs一样, 都是很适合剪枝的哦!)
剪枝1: pattern中没有1号城市的可以跳过
剪枝2: pattern中没有j, 但是要求此时在j城市的可以跳过

时间复杂度: \(O(n^22^n)\) 跑不满

AC代码:

/*
Author: SJ
*/
#include<bits/stdc++.h>
const int N = 1e5 + 10;
const int INF = 1e9 + 7;
using ll = long long;
using ull = unsigned long long;

using namespace std;

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

  //freopen("data.in", "r", stdin);
  //freopen("data.ans", "w", stdout);

  int n;
  cin >> n;

  vector<vector<int>> a(n, vector<int>(n, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> a[i][j];
    }
  }

  vector<vector<int>> f((1 << n), vector<int>(n, INF));
  f[1][0] = 0;
  for (int i = 1; i < (1 << n); i++) {
    if (!(i & 1)) continue;
    for (int j = 0; j < n; j++) {
      if (!(i & (1 << j))) continue;

      for (int k = 0; k < n; k++) {
        if (j != k && (i & (1 << k))) {
          f[i][j] = min(f[i][j], f[i - (1 << j)][k] + a[k][j]);
        }
      }
    }
  }

  int ans = INF;
  for (int i = 0; i < n; i++) {
    ans = min(f[(1 << n) - 1][i] + a[i][0], ans);
  }
  cout << ans;
  return 0;
}

坑点1: 枚举合法前继时, 注意j == k的情况(其实不用)