Yuzhen's Blog

Yuzhen Qin

题解:P10447 最短 Hamilton 路径

5
2024-06-17

题意

给定一张 n 个点的带权无向图,点从 0 \rightarrow n-1 标号,求起点 0 到终点 n-1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0n-1 不重不漏地经过每个点恰好一次。

做法

暴搜是 O(n!) 的,会爆炸。考虑状压DP,设 dp[i][j] 为目前在 j 号点,访问过的点的方案为 i 的最小费用,其中 i 是一个 2^n 的状态。

每次枚举从起点和终点以及当前状态。注意边界和限制,当前状态是否与枚举的点冲突(起点没来过或者终点去过)。起点一定是 0,终点一定是 n-1

每次加上边权转移即可。

完整代码

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

#define ll long long

int a[20][20], f[1 << 20][20];

int main(void) {
	int n;
	cin >> n;
	
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			cin >> a[i][j];

	memset(f, 0x3f, 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] + a[k][j]);
		
	cout << f[(1 << n) - 1][n - 1] << endl;
	
	return 0;
}