2010年02月09日星期二.pku2288
狀態(tài)壓縮動態(tài)規(guī)劃，求一個特殊要求的哈密頓路徑，注意使用long long
和判斷只有一個節(jié)點的情況
推薦一篇講這個的文章
http://m.shnenglu.com/EyeOfProvidence/archive/2010/01/10/105356.html
1
2 #define bin(x) (1 <<(x))
3 const int N = 13;
4 int g[N][N],mask;
5 LL val[N];
6 LL stat[bin(N)][N][N]; //value of the path
7 LL cnt[bin(N)][N][N];
8 int m, n, sum;
9 void post()
10 {
11 memset(g, 0, sizeof(g));
12 memset(stat, 0, sizeof(stat));
13 memset(cnt, 0, sizeof(cnt));
14 sum = 0;
15 }
16
17 int main()
18 {
19 int i, j, k, testcase, a, b, u, v, w;LL fac;
20 scanf("%d", &testcase);
21 while (testcase--) {
22 scanf("%d%d", &n, &m);
23 for (i = 0; i < n; i++) {
24 scanf("%lld", val + i);
25 sum += val[i];
26 }
27 for (i = 0; i < m; i++) {
28 scanf("%d%d", &a, &b),a--,b--;
29 g[a][b] = g[b][a] = 1;
30 }
31 if (n == 1) { //!!
32 printf("%lld 1\n",val[0]);
33 post(); continue;
34 }
35 for (u = 0; u < n; u++) {
36 for (v = 0; v < n; v++) {
37 if (g[u][v]) {
38 cnt[bin(u) | bin(v)][u][v] = 1;
39 stat[bin(u) | bin(v)][u][v] = val[u] * val[v];
40 }
41 }
42 }
43 int mask = bin(n)-1;
44 for (i = 0; i <= mask; i++) {
45 for (u = 0; u < n; u++) {
46 for (v = 0; v < n; v++) {
47 if (cnt[i][u][v]) {
48 for (w = 0; w < n; w++) {
49 if (g[v][w] && !(i & bin(w))) {
50 fac = val[v] * val[w];
51 if (g[u][w]) { fac += val[u] * val[v] * val[w]; }
52 if (stat[i | bin(w)] [v][w] < stat[i][u][v] + fac) {
53 stat[i | bin(w)][v][w] = stat[i][u][v] + fac;
54 cnt[i | bin(w)][v][w] = cnt[i][u][v];
55 } else if (stat [i | bin(w)][v][w] == stat[i][u][v] + fac) {
56 cnt[i | bin(w)][v][w] += cnt[i][u][v];
57 }
58 }
59 }
60 }
61 }
62 }
63 }
64 LL res1 = 0, res2 = 0;
65 for (j = 0; j < n; j++) {
66 for (k = 0; k < n; k++) {
67 if (res1 < stat[mask][j][k]) {
68 res1 = stat[mask][j][k];
69 res2 = cnt[mask][j][k];
70 } else if (res1 == stat[mask][j][k]) {
71 res2 += cnt[mask][j][k];
72 }
73 }
74 }
75 if (res1) { res1 += sum; }
76 cout << res1 <<' ' << res2 / 2 << endl;
77 post();
78 }
79 return 0;
80 }