题目链接:
https://vjudge.net/contest/159644#problem/E
题意:
有n个点，每个点都有一个价值，无论从哪个点走，要求每个点只能走一次【哈密顿通路】，求出怎么走使得到的价值最大，且求出最大价值的路有多少条。假设有4个点，它的最大走法是1–>4–>2–>3,且1,4,2三点可以形成三角形，4,2,3也可以形成三角形，那么最大价值为：v[1]+v[4]+v[2]+v[3]+v[1]*v[4]+v[4]*v[2]+v[1]*v[4]*v[2]+v[2]*v[3]+v[4]*v[2]*v[3]
题解:
http://www.cnblogs.com/jackge/archive/2013/05/24/3096162.html
dp[state][i][j]表示state状态下倒数第二个岛为i，最后一个岛为j时的最优解，num[state][i][j]为相应的路径数目，其中state的二进制表示的i位为1表示岛i被访问过，反之为0。
如果状态（state,i,j）可达，检查岛k，如果此时k没有被访问过并且有边(j,k)存在，则做如下操作：
1）设tmp为下一步访问岛k时获得的总利益，now=state+(1<<k)。
2）如果t,p>dp[next][j][k]，表示此时可以更新到更优解，则更新：
dp[now][j][k]=q,num[now][j][k]=num[state][i][j]。
3）如果tmp==dp[now][j][k]，表示此时可以获得达到局部最优解的更多方式，则更新：
num[now][j][k]+=num[sta][i][j]。
最后检查所有的状态（(1<<n)-1,i,j），叠加可以得到最优解的道路数。
需要注意的是，题目约定一条路径的两种行走方式算作一种，所以最终结果要除2。
代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 typedef long long ll; 6 #define MS(a) memset(a,0,sizeof(a)) 7 #define MP make_pair 8 #define PB push_back 9 const int INF = 0x3f3f3f3f; 10 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 11 inline ll read(){ 12 ll x=0,f=1;char ch=getchar(); 13 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 14 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 15 return x*f; 16 } 17 ////////////////////////////////////////////////////////////////////////// 18 const int maxn = 1e5+10; 19 20 int val[15],g[15][15],dp[(1<<13)][15][15],num[(1<<13)][15][15]; 21 22 int main(){ 23 int T = read(); 24 while(T--){ 25 MS(g); 26 int n,m; cin>>n>>m; 27 for(int i=0; i<n; i++) cin>>val[i]; 28 for(int i=0; i<m; i++){ 29 int u,v; cin>>u>>v; 30 u--,v--; 31 g[u][v] = g[v][u] = 1; 32 } 33 34 memset(dp,-1,sizeof(dp)); 35 memset(num,0,sizeof(num)); 36 37 if(n == 1){ 38 cout << val[0] << " " << 1 << endl; 39 continue; 40 } 41 42 for(int i=0; i<n; i++) 43 for(int j=0; j<n; j++) 44 if(g[i][j] && i!=j){ 45 dp[(1<<i)+(1<<j)][i][j] = val[i]+val[j]+val[i]*val[j]; 46 num[(1<<i)+(1<<j)][i][j] = 1; 47 } 48 for(int sta=0; sta<(1<<n); sta++){ 49 for(int i=0; i<n; i++){ 50 if(sta&(1<<i)){ 51 for(int j=0; j<n; j++){ 52 if((sta&(1<<j)) && g[i][j] && i!=j){ 53 for(int k=0; k<n; k++){ 54 if((sta&(1<<k))==0 && g[j][k] && i!=k && j!=k && dp[sta][i][j]!=-1){ 55 int tmp = dp[sta][i][j]+val[k]+val[j]*val[k]; 56 if(g[i][k]) tmp += val[i]*val[j]*val[k]; 57 if(tmp > dp[sta|(1<<k)][j][k]){ 58 dp[sta|(1<<k)][j][k] = tmp; 59 num[sta|(1<<k)][j][k] = num[sta][i][j]; 60 } 61 else if(tmp == dp[sta|(1<<k)][j][k]) 62 num[sta|(1<<k)][j][k] += num[sta][i][j]; 63 } 64 } 65 } 66 } 67 } 68 } 69 } 70 71 int ans1 = 0; ll ans2 = 0; 72 for(int i=0; i<n; i++){ 73 for(int j=0; j<n; j++){ 74 if(i!=j && g[i][j]){ 75 if(ans1 < dp[(1<<n)-1][i][j]){ 76 ans1 = dp[(1<<n)-1][i][j]; 77 ans2 = num[(1<<n)-1][i][j]; 78 }else if(ans1==dp[(1<<n)-1][i][j]){ 79 ans2 += num[(1<<n)-1][i][j]; 80 } 81 } 82 } 83 } 84 cout << ans1 << " " << ans2/2 << endl; 85 } 86 87 return 0; 88 } 89 90 // http://www.cnblogs.com/jackge/archive/2013/05/24/3096162.html