Posts Tagged ‘哈密顿回路’

POJ 2288 Islands and Bridges

Posted in PKU OJ on 四月 8th, 2010 by 纳米 – Be the first to comment

2009-12-02，AC

解题报告：
哈密顿回路是NPC问题。但是由于n<=13，可以采取状态压缩DP解决。
每个状态按照题目给出要求转移就可以了。注意要使用long long。

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
const int maxn = 13, maxm = 157, maxpow = 8193;
const int pow[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192};
 
int n, m, edge[maxn][maxn + 2], list[maxm][2];
long long data[maxn], dp[maxpow][maxn][maxn], dp_c[maxpow][maxn][maxn];
bool exist[maxn][maxn];
struct __ZT{
	int s, size;
	bool exist[maxn];
} ZT[maxpow], zt[maxpow];
long long answer, answer_c;
 
int init() {
	for (int i = 1; i < pow[maxn]; ++i) {
		ZT[i].s = i;
		ZT[i].size = 0;
		memset(ZT[i].exist, 0, maxn);
		for (int j = 0; j < maxn; ++j)
			if (pow[j] & i) {
				ZT[i].exist[j] = 1;
				++ZT[i].size;
			}
	}
	return 0;
}
 
int input() {
	memset(exist, 0, sizeof(exist));
	memset(edge, 0, sizeof(edge));
 
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i)
		scanf("%I64d", &data[i]);
	for (int i = 1; i <= m; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		if (u != v) {
			--u;--v;
			exist[u][v] = exist[v][u] = 1;
		}
	}
	int j = 0;
	for (int u = 0; u < n; ++u)
		for (int v = 0; v < n; ++v)
			if (exist[u][v]) {
				edge[u][++edge[u][0]] = v;
				list[j][0] = u;
				list[j][1] = v;
				++j;
			}
	m = j;
	return 0;
}
 
int comp(__ZT *x, __ZT *y) {
	return x->size - y->size;
}
 
int work() {
	if (n == 1) {
		answer = data[0];
		answer_c = 1;
	} else if (n == 2) {
		if (exist[0][1]) {
			answer = data[0] + data[1] + data[0] * data[1];
			answer_c = 1;
		} else {
			answer = answer_c = 0;
		}
	} else {
		memcpy(zt, ZT, sizeof(__ZT) * pow[n]);
		qsort(&zt[1], pow[n] - 1, sizeof(__ZT), (int(*) (const void*, const void*)) comp);
		memset(dp, 0, sizeof(dp));
		for (int i = 0; i < m; ++i) {
			int u = list[i][0], v = list[i][1];
			int A = pow[u] + pow[v];
			dp[A][u][v] = data[u] * data[v];
			dp_c[A][u][v] = 1;
		}
		for (int i = (n * n + n) / 2 + 1; i < pow[n]; ++i) {
			int A = zt[i].s;
			for (int j = 0; j < m; ++j) {
				int u = list[j][0], v = list[j][1];
				if (zt[i].exist[u] && zt[i].exist[v]) {
					int B = A - pow[v];
					for (int k = 1, w = edge[u][1]; k <= edge[u][0]; w = edge[u][++k])
						if (pow[w] & B && dp[B][w][u]) {
							long long x = dp[B][w][u] + (exist[w][v] ? data[u] * data[v] * data[w] : 0);
							if (x > dp[A][u][v]) {
								dp[A][u][v] = x;
								dp_c[A][u][v] = dp_c[B][w][u];
							} else if (x == dp[A][u][v]) {
								dp_c[A][u][v] += dp_c[B][w][u];
							}
						}
					if (dp[A][u][v])
						dp[A][u][v] += data[u] * data[v];
				}
			}
		}
		answer = 0;
		int A = pow[n] - 1;
		for (int i = 0; i < m; ++i) {
			int u = list[i][0], v = list[i][1];
			if (dp[A][u][v] > answer) {
				answer = dp[A][u][v];
				answer_c = dp_c[A][u][v];
			} else if (dp[A][u][v] == answer) {
				answer_c += dp_c[A][u][v];
			}
		}
		if (answer) {
			for (int i = 0; i < n; ++i)
				answer += data[i];
			answer_c >>= 1;
		} else {
			answer = answer_c = 0;
		}
	}
	return 0;
}
 
int output() {
	printf("%I64d %I64d\n", answer, answer_c);
	return 0;
}
 
int main() {
	init();
	int T;
	scanf("%d", &T);
	for (int i = 1; i <= T; ++i) {
		input();
		work();
		output();
	}
	return 0;
}