#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m; int val[15],map[13][13]; int dp[1<<13][13][13]; //dp[state][i][j]表示state状态下倒数第二个岛为i，最后一个岛为j时的最优解 long long num[1<<13][13][13]; //num[state][i][j]为相应的路径数目 int main(){ //freopen("input.txt","r",stdin); int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&val[i]); memset(map,0,sizeof(map)); int u,v; while(m--){ scanf("%d%d",&u,&v); u--;v--; map[u][v]=map[v][u]=1; } if(n==1){ printf("%d 1 ",val[0]); continue; } memset(dp,-1,sizeof(dp)); memset(num,0,sizeof(num)); for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i!=j && map[i][j]){ dp[(1<<i)|(1<<j)][i][j]=val[i]+val[j]+val[i]*val[j]; num[(1<<i)|(1<<j)][i][j]=1; } for(int i=0;i<(1<<n);i++) for(int j=0;j<n;j++) if((i&(1<<j))!=0) for(int k=0;k<n;k++) if(map[j][k] && j!=k && (i&(1<<k))!=0 && dp[i][j][k]!=-1) //这里得注意，先彻底明白该dp[][][]的具体含义， for(int x=0;x<n;x++) if(map[k][x] && j!=x && k!=x && (i&(1<<x))==0){ int tmp=dp[i][j][k]+val[x]+val[k]*val[x]; if(map[j][x]) tmp+=val[j]*val[k]*val[x]; if(dp[i|(1<<x)][k][x]<tmp){ dp[i|(1<<x)][k][x]=tmp; num[i|(1<<x)][k][x]=num[i][j][k]; }else if(dp[i|(1<<x)][k][x]==tmp) num[i|(1<<x)][k][x]+=num[i][j][k]; } int ans1=0; long long ans2=0; for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i!=j && map[i][j]){ if(ans1<dp[(1<<n)-1][i][j]){ ans1=dp[(1<<n)-1][i][j]; ans2=num[(1<<n)-1][i][j]; }else if(ans1==dp[(1<<n)-1][i][j]) ans2+=num[(1<<n)-1][i][j]; } cout<<ans1<<" "<<ans2/2<<endl; } return 0; }
这是一道典型的利用状态压缩DP求最优Hamilton回路的题目。
取dp[state][i][j]表示state状态下倒数第二个岛为i，最后一个岛为j时的最优解，num[state][i][j]为相应的路径数目，其中state的二进制表示的i位为1表示岛i被访问过，反之为0。
则显然当有边(i,j)存在时，有如下初值可赋：
dp[(1<<i)+(1<<j)][i][j]=val[i]+val[j]+val[i]*val[j],num[(1<<i)+(1<<j)][i][j]=1。
如果状态（state,i,j）可达，检查岛k，如果此时k没有被访问过并且有边(j,k)存在，则做如下操作：
1）设tmp为下一步访问岛k时获得的总利益，r=state+(1<<k)。
2）如果t,p>dps[r][j][k]，表示此时可以更新到更优解，则更新：
dp[r][j][k]=q,num[r][j][k]=num[state][i][j]。
3）如果tmp==dp[r][j][k]，表示此时可以获得达到局部最优解的更多方式，则更新：
num[r][j][k]+=num[p][i][j]。
最后检查所有的状态（(1<<n)-1,i,j），叠加可以得到最优解的道路数。
需要注意的是，题目约定一条路径的两种行走方式算作一种，所以最终结果要除2。
取dp[state][i][j]表示state状态下倒数第二个岛为i，最后一个岛为j时的最优解，num[state][i][j]为相应的路径数目，其中state的二进制表示的i位为1表示岛i被访问过，反之为0。
则显然当有边(i,j)存在时，有如下初值可赋：
dp[(1<<i)+(1<<j)][i][j]=val[i]+val[j]+val[i]*val[j],num[(1<<i)+(1<<j)][i][j]=1。
如果状态（state,i,j）可达，检查岛k，如果此时k没有被访问过并且有边(j,k)存在，则做如下操作：
1）设tmp为下一步访问岛k时获得的总利益，r=state+(1<<k)。
2）如果t,p>dps[r][j][k]，表示此时可以更新到更优解，则更新：
dp[r][j][k]=q,num[r][j][k]=num[state][i][j]。
3）如果tmp==dp[r][j][k]，表示此时可以获得达到局部最优解的更多方式，则更新：
num[r][j][k]+=num[p][i][j]。
最后检查所有的状态（(1<<n)-1,i,j），叠加可以得到最优解的道路数。
需要注意的是，题目约定一条路径的两种行走方式算作一种，所以最终结果要除2。