不难写出转移方程, \(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的情况(其实不用)