介绍
通过图G经过所有的节点，且所有的节点仅经过一次的通路，就是哈密顿通路。
题意
有N座岛，M座桥，让你找到一条哈密顿通路，当经过一座岛就加上该岛的价值，如果相邻两岛之间有桥再加上两岛价值之积，如果相邻三岛之间两两都有桥，再加上三岛价值之积。求最大总价值是多少以及达到最大总价值的路径有几条。
思路
这道题还算一个比较中规中矩的状压DP入门题。就是得设计两个状态转移方程，所以有写麻烦。
两个状态转移方程都是代表在这次选了j节点上次选了k节点而达到了 i+sta[j] 状态。dp_v 用来存该情况下最大总价值，dp_n用来存达到同种情况下的达到最大总价值的方案数。
dp_v[i+sta[j]][j][k]=max(dp_v[i][k][z]+V(经过这个点所带的总价值));
dp_n[i+sta[j]][j][k]+=dp[i][k][z];
注意：N==1时；用__int64保存；T组数据；方案数除以2。
代码如下：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<queue>
using namespace std;
int sta[15]= {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};
__int64 dp_n[1<<13][13][13];
__int64 dp_v[1<<13][13][13];
bool flag[1<<13][13][13];//入队列时进行标记，否则会造成重复入队列，会超内存
int N,M,val[15],g[15][15];
__int64 ans_1,ans_2;
struct node
{
short i,j,k;
};
void init()//初始化
{
memset(g,0,sizeof(g));
memset(dp_n,0,sizeof(dp_n));
memset(dp_v,-1,sizeof(dp_v));
memset(flag,0,sizeof(flag));
}
queue<node>q;
void solve()
{
node temp;
for(int i=0; i<N; ++i)
{
temp.i=sta[i];
temp.j=i;
temp.k=i;
flag[temp.i][temp.j][temp.k]=1;
dp_n[temp.i][temp.j][temp.k]=1;
dp_v[temp.i][temp.j][temp.k]=val[i];
q.push(temp);
}
while(!q.empty())
{
int i=q.front().i;
int j=q.front().j;
int k=q.front().k;
flag[i][j][k]=0;
q.pop();
for(int z=0; z<N; ++z)
{
if(g[j][z]&&((i&sta[z])==0))
{
temp.i=i+sta[z];
temp.j=z;
temp.k=j;
__int64 temp_v;
temp_v=dp_v[i][j][k]+val[z]+val[z]*val[j];
if(g[z][k]&&k!=j)
temp_v+=val[z]*val[j]*val[k];
if(dp_v[temp.i][temp.j][temp.k]==temp_v)
{
dp_n[temp.i][temp.j][temp.k]+=dp_n[i][j][k];
if(temp.i<sta[N]-1&&flag[temp.i][temp.j][temp.k]==0)
{
q.push(temp);
flag[temp.i][temp.j][temp.k]=1;
}
}
if(dp_v[temp.i][temp.j][temp.k]<temp_v)
{
dp_v[temp.i][temp.j][temp.k]=temp_v;
dp_n[temp.i][temp.j][temp.k]=dp_n[i][j][k];
if(temp.i<sta[N]-1&&flag[temp.i][temp.j][temp.k]==0)
{
q.push(temp);
flag[temp.i][temp.j][temp.k]=1;
}
}
}
}
}
for(int j=0; j<N; ++j)
{
for(int k=0; k<N; ++k)
{
if(dp_v[sta[N]-1][j][k]!=-1)
{
temp.i=sta[N]-1;
temp.j=j;
temp.k=k;
if(ans_1<dp_v[temp.i][temp.j][temp.k])
{
ans_1=max(ans_1, dp_v[temp.i][temp.j][temp.k]);
ans_2=0;
ans_2=dp_n[temp.i][temp.j][temp.k];
}
else if(ans_1==dp_v[temp.i][temp.j][temp.k])
ans_2+=dp_n[temp.i][temp.j][temp.k];
}
}
}
if(N==1)//当N为1时特殊处理
ans_2=2;
printf("%I64d %I64d
",ans_1,ans_2/2);//因为不算顺序，正反一样，所以应该除2，
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
init();
scanf("%d%d",&N,&M);
int v,x,y;
for(int i=0; i<N; ++i)
{
scanf("%d",&val[i]);
}
for(int i=0; i<M; ++i)
{
scanf("%d%d",&x,&y);
--x;
--y;
g[x][y]=1;
g[y][x]=1;
}
ans_1=0;
ans_2=0;
solve();
}
return 0;
}