哈密顿路径问题：
一般设 表示
状态下，
为最后一个最值情况 。
一般有两种稍微不同的写法，单纯就是写法不同，思路方法都相同。
第一个例题为第一种转移方法，有当前转移后面。
后面的都是由前面转移目前。
G. Shuffling Songs
题意：就是要你删除最少的歌曲，使其播放精彩,每对相邻的歌曲要么作者相同，要么流派相同(或两者皆有)即为精彩。
思路：观察数据范围可以发现2的16次方枚举，类似哈密顿路劲问题转移即可
string g[N], s[N];
int n;
void solve()
{cin >> n;for (int i = 0; i < n; i++)cin >> g[i] >> s[i];vector<int> e(n, 0);for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (g[i] == g[j] || s[i] == s[j])e[i] |= (1 << j);}}vector<vector<int>> f(1 << n, vector<int>(n, 0));for (int i = 0; i < n; i++)f[1 << i][i] = 1;for (int i = 0; i < (1 << n); i++){for (int j = 0; j < n; j++) // 最后一个点是谁{if (!f[i][j])continue;for (int k = 0; k < n; k++){if (i >> k & 1) // 加进去一个点continue;if ((e[j] >> k) & 1){f[i | (1 << k)][k] = 1;}}}}int ans = 0;for (int i = 0; i < (1 << n); i++){for (int j = 0; j < n; j++)if (f[i][j])ans = max(ans, __builtin_popcount(i));}cout << n - ans << endl;
}
AcWing 731. 毕业旅行问题
同理也是哈密顿路径问题
int g[M][M];
int f[1 << 20][20];
void solve()
{int n;cin >> n;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cin >> g[i][j];memset(f, inf, sizeof f);f[1][0] = 0;for (int i = 0; i < (1 << n); i++){for (int j = 0; j < n; j++){if (i >> j & 1){for (int k = 0; k < n; k++){if (i - (1 << j) >> k & 1){f[i][j] = min(f[i][j], f[i - (1 << j)][k] + g[k][j]);}}}}}int ans = 1e18;for (int i = 1; i < n; i++)ans = min(ans, f[(1 << n) - 1][i] + g[i][0]);cout << ans << endl;
}91. 最短Hamilton路径
int f[1 << 20][21];
int g[M][M];
void solve()
{int n;cin >> n;for (int i = 0; i < n; i++){for (int j = 0; j < n; j++)cin >> g[i][j];}memset(f, 0x7f, sizeof f);f[1][0] = 0;for (int i = 0; i < (1 << n); i++){for (int j = 0; j < n; j++){if (i >> j & 1){for (int k = 0; k < n; k++){if (i - (1 << j) >> k & 1){f[i][j] = min(f[i - (1 << j)][k] + g[k][j], f[i][j]);}}}}}cout << f[(1 << n) - 1][n - 1] << endl;
}
