1
#include <iostream>
2using namespace std;
3
4
5const int inf = 1<<14;
6int n, ma;
7__int64 dp[inf][14][14], way[inf][14][14];
8int v[14];
9bool m[14][14];
10
11
12int main()
13
{
14
int qq;
15 scanf("%d",&qq);
16 while (qq--)
17
{
18 scanf("%d %d",&n, &ma);
19 for (int i = 0; i < n; ++i)
20 scanf("%d",&v[i]);
21 memset(m,false,sizeof(m));
22 memset(dp,-1,sizeof(dp));
23 memset(way,0,sizeof(way));
24 int x, y;
25 for (int i = 0; i < ma; ++i)
26 {
27 scanf("%d %d",&x,&y);
28 m[x-1][y-1] = true;
29 m[y-1][x-1] = true;
30
}
31
32 //dp
33 for (int i = 0; i < n; ++i)
34 for (int j = 0; j < n; ++j)
35 {
36 if (i != j && m[i][j])
37 {
38 dp[(1<<i) + (1<<j)][i][j] = v[i]+v[j]+v[i]*v[j];
39 way[(1<<i) + (1<<j)][i][j] = 1;
40 }
41 }
42 int s = 1<<(n);
43 for (int p = 3; p < s; ++p)
44 for (int i = 0; i < n; ++i)
45 if (p&(1<<i))
46 for (int j = 0; j < n; ++j)
47 {
48 if ((p&(1<<j)) && i != j && dp[p][i][j] > -1)
49 {
50 for (int k = 0; k < n; ++k)
51 {
52 if ((p&(1<<k)) == 0 && m[j][k])
53 {
54 int r = p + (1<<k);
55 int q;
56 if (m[i][k])
57 q = dp[p][i][j] + v[k] + v[j]*v[k] + v[i]*v[j]*v[k];
58 else
59 q = dp[p][i][j] + v[k] + v[j]*v[k];
60 if (q > dp[r][j][k])
61 {
62 dp[r][j][k] = q;
63 way[r][j][k] = way[p][i][j];
64 }
65 else if (q == dp[r][j][k])
66 way[r][j][k] += way[p][i][j];
67
68 }
69 }
70 }
71 }
72 __int64 maxv = -1, maxw = 0;
73 int p = (1<<(n)) - 1;
74 for (int i = 0; i < n; ++i)
75 for (int j = 0; j < n; ++j)
76 {
77 if (maxv < dp[p][i][j])
78 {
79 maxv = dp[p][i][j];
80 maxw = way[p][i][j];
81 }
82 else
83 if (maxv == dp[p][i][j])
84 maxw += way[p][i][j];
85 }
86 if (n == 1)
87 {
88 maxv = v[0];
89 maxw = 2;
90 }
91 if (maxv == -1)
92 printf("0 0\n");
93 else
94 printf("%I64d %I64d\n",maxv, maxw/2);
95 }
96 return 0;
97
}
dp[p][i][j] p的二进制表示当前路径上的点，i，j表示最后经过的两个点。
posted on 2011-04-03 21:31
sweet empyrean 阅读(137)
评论(0) 编辑 收藏 引用 所属分类:
POJ