poj 2288(状压DP)

poj 2288
题意:求一个无向图中的一条哈密顿路,这条路价值最大。
价值计数方法为:所有点权+两连续点权积+三连续点构成三角形积 (算法竞赛进阶指南例题)

这种方程的转移能力还是差。。
设$dp(S,i,j)$为状态为$S$,最后访问的两个点依次为$i,j$的最大值
那么转移就是$dp(S,i,j)=dp(S-k,j,k)+val_i+val_i \cdot val_j$,如果$i,k$连通则加上$val_i \cdot val_j \cdot val_k$
这个转移相当于当前路径是$k->j->i$,从$(k,j)$转移到$(j,i)$

初始化$dp(S, i, j) = val_i + val_j + val_i \cdot val_j$,两点连通对答案的贡献
然后之后的 DP 都从这些转移过来,记得判无效状态!

知识点:
1、DP检查方法: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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
LL n, m, val[15], G[15][15], dp[(1 << 13) + 5][15][15], cnt[(1 << 13) + 5][15][15];
void clean() {
ms(G, 0), ms(dp, 0), ms(cnt, 0);
}
int solve() {
scanf("%lld%lld", &n, &m);
clean();
for (LL i = 1; i <= n; ++i) scanf("%lld", &val[i]);
if (n == 1) return printf("%lld %lld\n", val[1], 1ll), 0;
for (LL a, b, i = 1; i <= m; ++i) {
scanf("%lld%lld", &a, &b);
G[a][b] = G[b][a] = 1;
}
for (LL u = 1; u <= n; ++u) {
for (LL v = 1; v <= n; ++v) if (u != v && G[u][v]) {
dp[(1 << (u - 1)) + (1 << (v - 1))][u][v] = val[u] * val[v] + val[u] + val[v];
cnt[(1 << (u - 1)) + (1 << (v - 1))][u][v] = 1;
//cerr << "???" << dp[(1 << (u - 1)) + (1 << (v - 1))][u][v] << " u" << u << " v" << v << endl;
}
}
for (LL S = 0; S < (1 << n); ++S) {
for (LL i = 1; i <= n; ++i) if (S & (1 << (i - 1))) {
for (LL j = 1; j <= n; ++j) if (i != j && S & (1 << (j - 1)) && G[i][j]) {
for (LL k = 1; k <= n; ++k) if (k != i && k != j && S & (1 << (k - 1)) && G[k][j] && dp[S ^ (1 << (i - 1))][j][k] > 0) {
LL whw = dp[S ^ (1 << (i - 1))][j][k] + val[i] + val[i] * val[j] + G[k][i] * val[i] * val[j] * val[k];
if (dp[S][i][j] < whw) {
dp[S][i][j] = whw;
cnt[S][i][j] = cnt[S ^ (1 << (i - 1))][j][k];
} else if (dp[S][i][j] == whw) cnt[S][i][j] += cnt[S ^ (1 << (i - 1))][j][k];
}
}
}
}
LL ans1 = 0ll, ans2 = 0ll;
for (LL i = 1; i <= n; ++i)
for (LL j = 1; j <= n; ++j) {
if (dp[(1 << n) - 1][i][j] > ans1) ans1 = dp[(1 << n) - 1][i][j], ans2 = cnt[(1 << n) - 1][i][j];
else if (dp[(1 << n) - 1][i][j] == ans1) ans2 += cnt[(1 << n) - 1][i][j];
}
printf("%lld %lld\n", ans1, ans2 / 2ll);
return 0;
}
}
int main() {
int q; scanf("%d", &q);
while (q--) flyinthesky::solve();
return 0;
}

------ 本文结束 ------