考察:状压dp
思路:
考虑到计算三角形,我们需要知道落脚点i和前一个落脚点j,所以需要三维数组.根据状态转移方程f[i][j][k] = f[i-{j}][k][t]+score很容易求出最大的权值.但是比较难想到怎么计算路径数目(对本蒟蒻而言).方法是再声明一个记录当前路径最大值的方案数组.状态转移方程是nums[i][j][k] = nums[i-{j}][k][t].如果两者最大值相等就是nums[i][j][k] += nums[i-{j}][k][t].数据应该不存在重边,不然网上答案都是错的.
注意:答案需要取到long long
再再注意:不要用f的值有没有改变去更新nums数组,这会WA到死...因为如果本次计算的值比最值小也会更新nums数组,实际上是不能更新的
再再再注意:计算的res计入了1->2->3和3->2->1,也就是存在一条的话它会把回头路也算进去
1 #include <iostream>
2 #include <cstring>
3 #include <algorithm>
4 #include <cstdio>
5 using namespace std;
6 typedef long long ll;
7 const int N = 14,INF = 0x3f3f3f3f;
8 bool mp[N][N];
9 int n,m,w[N],f[1<<N][N][N],ans;
10 ll nums[1<<N][N][N],res;
11 void inits()
12 {
13 memset(mp,0,sizeof mp);
14 ans = 0; res = 0; memset(nums,0,sizeof nums);
15 memset(f,0,sizeof f);
16 }
17 int main()
18 {
19 int T;
20 scanf("%d",&T);
21 while(T--)
22 {
23 scanf("%d%d",&n,&m);
24 inits();
25 int all = (1<<n)-1;
26 for(int i=1;i<=n;i++) scanf("%d",&w[i-1]);
27 if(n==1) { printf("%d %d\n",w[n-1],1);continue;}
28 for(int i=1;i<=m;i++)
29 {
30 int a,b; scanf("%d%d",&a,&b);
31 a--,b--;
32 mp[a][b] = mp[b][a] = 1;
33 int tmp = (1<<a)|(1<<b);
34 f[tmp][b][a] = f[tmp][a][b] = w[a]+w[b]+w[a]*w[b];
35 nums[tmp][b][a] = nums[tmp][a][b] = 1;
36 }
37 for(int i=0;i<1<<n;i++)
38 for(int j=0;j<n;j++)
39 if(i>>j&1)
40 for(int k=0;k<n;k++)
41 if(((i-(1<<j)>>k)&1)&&(mp[j][k]))
42 for(int t=0;t<n;t++)
43 if(((i-(1<<j)-(1<<k))>>t&1)&&(mp[k][t]))
44 {
45 if(!nums[i-(1<<j)][k][t]) continue;
46 int score = w[j]+w[j]*w[k];
47 if(mp[j][t]) score+=w[j]*w[t]*w[k];
48 int val = f[i-(1<<j)][k][t]+score;
49 if(val>f[i][j][k]) f[i][j][k] = val,nums[i][j][k] = nums[i-(1<<j)][k][t];
50 else if(val==f[i][j][k]) nums[i][j][k] += nums[i-(1<<j)][k][t];
51 }
52 for(int i=0;i<n;i++)
53 for(int j=0;j<n;j++)
54 if(ans<f[all][i][j]) ans = f[all][i][j],res = nums[all][i][j];
55 else if(ans==f[all][i][j]) res+=nums[all][i][j];
56 printf("%d %lld\n",ans,res/2);
57 }
58 return 0;
59 }