POJ 2288 Islands and Bridge 状压DP

缘起

继续学习状压DP~ POJ 2288 Islands and Bridge

分析

1
2
3
4
5
6
7
8
在一个无向图中G(V,E)中(n=|V|<=13)，每一个点有一个点权，并有哈密顿路径（指从起点开始不重复经过一点到终点的路径）。

现在规定哈密顿路径的代价由三部分构成：
1,所有的点权之和；
2,哈密顿路径中相邻点点权乘积之和；
3,哈密顿路径中相邻的三个点在原图中若形成环(即形成一个三角形)，则3的答案加上这三个点的乘积。

1式+2式+3式即为这条哈密顿路径的代价。如果还不懂题意：请看下图：
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
问题为：求出最大哈密顿路径的代价与哈密顿路径的方案数。规定：路径1-2-3与3-2-1是一样的，但1-2-3与2-3-1
是不一样的。

【输入】
多样例, 第一行是样例数. 每个样例开始于n和m,表示顶点的个数和边的数目.然后是n个正整数（<=100）, 分别
表示每个顶点的权值. 然后是m行，每行是x y, 表示一条边x---y. 顶点的标号从1到n,n<=13

【输出】
对每个样例.输出两个整数，第一个是最大的代价, 第二个是条数. 如果样例不存在哈密顿路径的话, 输出0 0

【样例输入】
2
3 3
2 2 2
1 2
2 3
3 1
4 6
1 2 3 4
1 2
1 3
1 4
2 3
2 4
3 4

【样例输出】
22 3
69 1

【限制】
4s 65535KB

注意, 本题是哈密顿路径，而非哈密顿回路. 哈密顿回路的话, 就是TSP类型的问题. 这在【1】中讨论过，其中就包含状压DP方法。 但是【1】中的思路还是可以借鉴的.

其实状压DP扩展状压的对象也不是随便扩展的, 而是一点一点有需要才扩展的. 首先模仿【1】, 我们知道令

1
2
3
4
5
6
7
8
9
10
11
12
13
dp[i][j] 是当前已经访问过的点集状压为i(0<=i<full:=1<<n)时, 当前位于j时的最大代价（为简单起见,先不
考虑路径数量）.
则考虑状态转移, 显然下一个要去的点位于i中. 假设是点k, 则自然我们知道i该怎么变——O(1)就能知道.假设变成了ii
而j显然变成了k. 然后计算代价.即dp[ii][k], 而我们必须要计算出走这一步我们赚取了多少代价. 
首先, 点k是有权的,假设是w(K),这是第一部分代价, 而且从j到k, 我们就知道赚取了 w(j)*w(k)
这是第二部分代价. 如果没有第三部分代价的话, 则本题和【1】都只需状压当前已经走过的顶点集和当前在哪个顶点集
就行了. 但是偏偏本题有第三部分代价——我们需要知道j,k以及j之前的那个点x三个点是否构成三角形, 亦即
k和x是否相连(所以本题应该使用邻接矩阵+邻接链表, 前者方便判断是否相邻,后者方便扩展状态). 看到了没有? 因此, 我们就不能仅仅状压已经遍历过的点集+当前位于那个点集, 还必须要状压
当前位于的点的前一个点x. 所以
令 dp[i][j][k] 为当前已经经历的点集为i, j是当前节点, j的前一个节点是k 这种状态下出发（开始计0）,
能达到的最大代价. 
则显然，我们要求的答案是 dp[0][0][0].
边界值是 dp[full-1][i][j] = 0, for all i!=j, 1<=i,j<=n

看到了吗? 其实状压DP到底要对什么东西进行状压, 就是在考虑状态转移的时候——什么不够加什么考虑过来的. 并非是一拍脑袋、一拍屁股想出来的. 本题还有两个问题要分析

Q: 怎么考虑最优解的方案数?

A: 只需要使用一个数组 dpp[i][j][k] 记录最优方案的数量，其中i、j、k的意义在上面已经说过了. 则我们显然要求的是dpp[0][0][0]

则考虑状态转移为 (ii, x, j) 的时候, dpp[i][j][k] 和dpp[ii][x][j] 之间的关系. 如果dp[ii][x][j] 是达到 dp[i][j][k] 的路的话, 则dpp[ii][x][j] 显然就要成为 dpp[i][j][k] 的一部分.

Q: 不存在哈密顿路径的话, 怎么判断?

A: 不需要特别处理的. 因为本题打算采用的是记忆化搜索（我DP个锤子~ 反正空间复杂度给得起~）.记忆化的时候, 即递归的时候, 如果能走到叶子的话（所谓叶子就是遍历完了所有的节点）, 因为每一步都是合法转移, 所以能到叶子的话, 则也就表示存在哈密顿路径. 对于到不了叶子的非叶子状态,则从该非叶子状态出发就不能形成哈密顿路径.

Q: 本题有什么注意事项吗?

A: 这一题非常多坑！！！首先，图有可能是不连通的，这时，要输出0 0（即对于不连通的图, 完全可以先跑dfs特判, 或者并查集特判而不需要傻傻跑状压DP浪费时间）；其次，图的点数有可能为1，这时，要输出v[1] 1；再其次，方案数有可能会爆int，还要用long long处理；再再其次，因为题目要求1-2-3和3-2-1是一样的，所以总方案数要除以2。

好了, 说了这么多, 愉快的切代码吧~

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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
typedef long long ll;
const int inf = 0x3f3f3f3f;
int n,m, g[15][15], w[15], dp[1<<13][15][15], f[15],full;
ll dpp[1<<13][15][15];

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 (fi>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;
}

inline int cost(int j, int k, int x) // j是当前顶点, k是j的前一个顶点, 从j转移到x, 产生的代价
{
	return w[x]+w[j]*w[x]+g[x][k]*w[j]*w[k]*w[x]; // x到k能连通
}

int kk(int i, int j, int k) // 求解dp[i][j][k]、dpp[i][j][k],反正空间复杂度允许, 我dp个锤子~
{
	if (~dp[i][j][k])
	{
		return dp[i][j][k];
	}
	if (i==full-1 && j!=k)
	{
		dpp[i][j][k] = 1;
		return dp[i][j][k] = 0;
	}
	for (int x = 0,t,nxti;x<n;x++)
	{
		if (i>>x&1 || !g[j][x+1]) // 注意, i的第0个比特位其实对应顶点1,所以x要+1	
		{
			continue;
		}
		nxti = i|1<<x; // 下一个顶点集状态
		t = kk(nxti, x+1, j) + cost(j,k,x+1);
		if (dp[i][j][k]==t)
		{
			dpp[i][j][k] += dpp[nxti][x+1][j];
		}
		else if (dp[i][j][k]<t)
		{
			dp[i][j][k] = t;
			dpp[i][j][k] = dpp[nxti][x+1][j];
		}
	}
	if (!~dp[i][j][k]) // 如果还是没走通, 说明从(i,j,k)这个状态出发是无法完成哈密顿路径的
	{
		dp[i][j][k] = -inf;
	}
	return dp[i][j][k];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		memset(g, 0, sizeof(g));
		memset(f, -1, sizeof(f));
		scanf("%d%d", &n,&m);
		full = 1<<n;
		for (int i = 1;i<=n;i++)
		{
			scanf("%d", w+i);
		}
		while(m--)
		{
			int x,y;
			scanf("%d%d", &x, &y);
			g[x][y] = g[y][x] = 1;
			merge(x,y);
		}
		for (int i = 1;i<=n;i++)
		{
			g[0][i] = 1;
		} // 可以从顶点0(虚拟的顶点)出发到达任何一个顶点（即哈密顿路径可以从任何顶点出发）,但是任何一个顶点不能回到虚拟顶点0
		if (n==1) // 特判只有一个顶点的情况
		{
			printf("%d %d\n", w[1], 1);
			continue;
		}
		if (!ck()) // 如果不连通,直接打印(0,0)走人, 不需要傻傻的状压DP去了
		{
			puts("0 0");
			continue;
		}
		memset(dp, -1, sizeof(dp));
		memset(dpp, -1, sizeof(dpp));
		kk(0,0,0);
		dp[0][0][0]<0?puts("0 0"):printf("%d %lld\n", dp[0][0][0], dpp[0][0][0]>>1); // 因为最后可能是-10亿多,这种情况是哈密顿路径不存在的情况
	}
	return 0;
}

ac情况

Status Accepted
Time 657ms
Memory 21760kB
Length 2278
Lang C++
Submitted 2019-11-03 08:37:02
Shared
RemoteRunId 21016671

参考

【1】https://yfsyfs.github.io/2019/09/05/hdu-5067-Harry-And-Dig-Machine-tsp%E9%97%AE%E9%A2%98/