题目大意：
有n个岛屿，令Vi为岛屿Ci的权值。一条汉密尔顿路径C1，C2，C3...Cn的值为3部分
第一部分，将路径中的岛的权值相加，第二部分将每条边上的(Ci,Cj),加上所有的Vi*Vj
第三部分，如果连续经过的3个城市可以形成3角联通，那么加上Vi*Vj*Vk
求出一条路径使其权值最大，并记录有多少可以达到最大权值的路径
1->2->3 , 3->2->1 视为相同路径
这里最多13个城市，所以用2进制表示是否到达当前位置的城市
这里用dp[i][k][j] 表示到达i状态时，最后到达的两个城市为j，k，这样可以达到的最大权值
dp[i|(1<<(t-1)][j][t] = max{dp[i|(1<<(t-1)][j][t] , dp[i][k][j]+val[t]+val[j]*val[t]+ edge[k][t]?val[j]*val[k]*val[t]:0}
注意每次更新dp值同时记录一个到达当前状态的路径数量cnt[i][k][j]
这里要注意只有一个城市的时候要特判
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <cmath> 5 using namespace std; 6 #define N 14 7 #define ll long long 8 int n,m; 9 ll dp[1<<N][N][N] , val[N] , cnt[1<<N][N][N];//cnt记录当前状态下可行的方法总数 10 bool edge[N][N]; 11 12 void getDp() 13 { 14 memset(cnt , 0 ,sizeof(cnt)); 15 memset(dp , -1 , sizeof(dp)); 16 int all = (1<<n); 17 dp[0][0][0]=0 , cnt[0][0][0]=0; 18 for(int i=1 ; i<=n ; i++) dp[1<<(i-1)][0][i]=val[i],cnt[1<<(i-1)][0][i]=1; 19 for(int i=1 ; i<all ; i++){ 20 for(int j=1 ; j<=n ; j++){ 21 if(!(i&(1<<(j-1)))) continue; 22 for(int k=0 ; k<=n ; k++){ 23 if(k == 0 && (i!=(1<<(j-1)))) continue; 24 if(k==j || (!(i&(1<<(k-1))) && k!=0)) continue; 25 if(dp[i][k][j]<0) continue; 26 27 for(int t=1 ; t<=n ; t++){ 28 if(!edge[j][t] || i&(1<<(t-1))) continue; 29 ll v = dp[i][k][j]+val[t]+val[t]*val[j]; 30 if(edge[t][k]) v = v+val[j]*val[k]*val[t]; 31 int status = i|(1<<(t-1)); 32 if(dp[status][j][t]<0 || dp[status][j][t]<v){ 33 dp[status][j][t]=v; 34 cnt[status][j][t]=cnt[i][k][j]; 35 } 36 else if(dp[status][j][t] == v){ 37 cnt[status][j][t]+=cnt[i][k][j]; 38 } 39 //debug 40 // print(status);cout<<endl; 41 // cout<<i<<" "<<j<<" "<<k<<" "<<dp[status][k][t]<<endl; 42 } 43 } 44 } 45 } 46 } 47 48 int main() 49 { 50 // freopen("a.in" , "r" , stdin); 51 int T; 52 scanf("%d" , &T); 53 while(T--) 54 { 55 scanf("%d%d" , &n , &m); 56 for(int i=1 ; i<=n ; i++) scanf("%I64d" , val+i); 57 memset(edge , 0 , sizeof(edge)); 58 int a,b; 59 for(int i=0 ; i<m ; i++){ 60 scanf("%d%d" , &a , &b); 61 edge[a][b]=true; 62 edge[b][a]=true; 63 } 64 getDp(); 65 int all=(1<<n); 66 ll maxn = -1 , ans=0; 67 for(int i=0 ; i<=n ; i++) 68 for(int j=0 ; j<=n ; j++) 69 { 70 maxn=max(maxn,dp[all-1][i][j]); 71 } 72 if(maxn == -1){ 73 puts("0 0"); 74 continue; 75 } 76 for(int i=0 ; i<=n ; i++) 77 for(int j=0 ; j<=n ; j++) 78 if(maxn == dp[all-1][i][j]) ans+=cnt[all-1][i][j]; 79 /***要注意只有一个城市的情况下要特判***/ 80 printf("%I64d %I64d " , maxn , ans/2?ans/2:1); 81 } 82 return 0; 83 }