HDU 3001 Traveling 状压DP

缘起

继续水状压DP~ HDU 3001 Traveling

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
n个城市, m条道路,无向图. 可以从任何一个城市出发. 但是一个城市不能经过2次. 每条边都有权重. 求
哈密顿路径的最小代价.

【输入】
多样例. 第一行两个整数n(1<=n<=10) and m， 然后m行，每行三个整数,a,b,c
1<=a,b<=n
表示a和b之间的权值是c

【输出】
最小代价, 如果不存在哈密顿路径, 输出-1

【样例输入】
2 1
1 2 100
3 2
1 2 40
2 3 50
3 3
1 2 3
1 3 4
2 3 10

【样例输出】
100
90
7 

【限制】
3s 32MB

如果做过【1】的话, 此题就是水题~ 因为本题连路径方法数都不需要考虑. 所以dp的对象仅仅是二维的. 但是和【1】不同之处在于本题每个点可以是0也可以是1,亦可以是2. 所以当前的状态宜用三进制刻画而不是二进制.

1
2
3
4
5
6
7
另dp[i][j] 是当前状态为i, 当前处于顶点j的时候, 从此状态出发(代价开始计0), 
后续形成哈密顿路径所需要的最小代价. 则答案就是 dp[0][0].
因为本题考虑使用记忆化搜索来做(依旧是 "空间复杂度给的起, 那我DP个锤子" 系列), 所以应该考虑递归出口. 
显然, 如果状态值i能保证每个3进制比特位都>=1的话, 则就是所有的城市都游历完了. 
ps: 等等, 其实三进制的操作显然没有4进制来的方便. 因为四进制能方便的使用位运算的技巧. 速度更快.
所以考虑使用四进制. 但是因为四进制会爆内存. 所以还是用3进制吧~
则 dp[i][j] = 0, 其中 1<=j<=n

话不多说, 开始愉快的切代码了~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
int n,m,dp[60000][12],f[12],g[12][12],pow3[12];
const int inf = 0x3f3f3f3f;
int getf(int i)
{
	return f[i]<0?i:f[i] = getf(f[i]);
}

void merge(int i, int j)
{
	int fi = getf(i), fj = getf(j);
	if (fi==fj)
	{
		return;
	}
	if (f[fi]>f[fj])
	{
		f[fj]+=f[fi];
		f[fi] = fj;
	}
	else
	{
		f[fi]+=f[fj];
		f[fj] = fi;
	}
}

bool ck()
{
	int tot = 0;
	for (int i = 1;i<=n;i++)
	{
		if (f[i]<0)
		{
			++tot;
		}
	}
	return tot==1;
}

int ckint[60000]; // 记忆化ck(int)的结果
int pow33[60000][10]; // pow33[i][j] 是i的第j个比特位

int ck(int i) // 检查i的每个比特位是不是都>=1, 一旦检查完毕, i的每个三进制比特位也都确定了
{
	if (~ckint[i])
	{
		return ckint[i];
	}
	for(int j = 0,t=i;j<n;j++)
	{
		if (!(pow33[i][j] = t%3))
		{
			ckint[i] = 0;
		}
		t/=3;
	}
	if (ckint[i])
	{
		ckint[i] = 1;
	}
	return ckint[i];
}

int kk(int i, int j)
{
	if (~dp[i][j])
	{
		return dp[i][j];
	}
	if (ck(i)) // 检查i是否每个比特位都>=1
	{
		return dp[i][j] = 0;
	}
	dp[i][j] = inf;
	for (int x = 0,nxti;x<n;x++)
	{
		if (j==x+1 || pow33[i][x]==2 || !~g[j][x+1]) // 三种情况不能从j转移到x+1 1. x+1就是j(自己不能转到自己) 2. x+1已经光顾两次了 3. 没有从j到x+1的路
		{
			continue;
		}
		nxti = i+pow3[x]; // 下一个状态
		dp[i][j] = min(dp[i][j], kk(nxti,x+1)+g[j][x+1]);
	}
	return dp[i][j];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	pow3[0] = 1;
	for (int i = 1;i<=10;i++)
	{
		pow3[i] = pow3[i-1]*3;
	}
	while(~scanf("%d%d", &n,&m))
	{
		memset(f,-1,sizeof(f));
		memset(g,-1,sizeof(g));
		memset(ckint, -1, sizeof(ckint));
		memset(pow33, -1, sizeof(pow33));
		memset(dp, -1, sizeof(dp)); // -1表示非法状态, 而inf 从(i,j)状态出发不能形成哈密顿路径
		while(m--)
		{
			int a,b,c;
			scanf("%d%d%d", &a, &b,&c);
			if (~g[a][b])
			{
				g[a][b] = g[b][a] = min(g[a][b], c); // 妈的, 此题有重边! wa了一发
			}
			else
			{
				g[a][b] = g[b][a] = c;
			}
			merge(a,b);
		}
		if (n==1) // 特判一个顶点的时候
		{
			puts("0");
			continue;
		}
		if (!ck())
		{
			puts("-1");
			continue;
		}
		for (int i = 1;i<=n;i++)
		{
			g[0][i] = 0;
		} // 0可以(无代价地)到达任何顶点i, 但是i不能回到0, 因为0毕竟就是个虚拟顶点
		kk(0,0);
		printf("%d\n", dp[0][0]<inf?dp[0][0]:-1); // 一开始这里写dp[0][0]<1e6, 1e6小了,wa了一发~
	}
	return 0;
}

ac情况

Status Accepted
Time 499ms
Memory 6624kB
Length 2191
Lang G++
Submitted 2019-11-03 11:25:55
Shared
RemoteRunId 31259637

参考

【1】https://yfsyfs.github.io/2019/10/31/POJ-2288-Islands-and-Bridge-%E7%8A%B6%E5%8E%8BDP/