链接
这题其实是 最短 \(Hamilton\) 路径， \(AcWing91/CH0103\) 的原版，\(ACM-ICPC\) \(Asia\) \(Regional\) \(Shanghai\) \(2004\) \(I\)题（加载较慢）， \(POJ2288\)。
给定点数 \(n \leqslant 13\) 、边数 \(m\) 、每点权值 \(w[i] \leqslant 100\) 还有边 \((x,y)\) （无向），求最大的 \(Hamilton\) 路径值以及最大值的走法数。具体求值操作如下：\(1.\) \(i\) 、 \(j\) 两点连通，则答案增加 \(w[i]*w[j]+w[i]+w[j]\) ;\(2.\) \(i\) 、 \(j\) 、\(k\) 三点均连通，则答案增加 \(w[i]*w[j]*w[k]\) 。
设 \(f[p][i][j]\) 表示状态为 \(p\) 时上两个走过的点为 \(i\) ，上一个走过的点为 \(j\) ， \(met[p][i][j]\) 表示左边情况下的方案数。 先预处理两点连通 \((g[i][j]==1)\) 的情况： \(f[(1<<i)|(1<<j)][i][j]=w[i]*w[j]+w[i]+w[j]\) ， \(met[(1<<i)|(1<<j)][i][j]=1\) 。 然后就愉快 \(dp\) 啦！在保证连通、未走过、 \(i\) 、 \(j\) 、 \(k\) 均不重复的情况下， $f[p|(1<<k)][j][k]=max \lbrace f[p][i][j]+w[k]+w[j]*w[k] (+w[三角形]) \rbrace $ ， \(met[p|(1<<k)][j][k]=met[p][i][j]\) \((f[p|(1<<k)][j][k]=f[p][i][j])\) 。
\(1.\) 数组大小：第一维要开 \(1<<13\) ，少了不够跑，多了 \(mle\) 。（好傻逼的错误啊）
\(2.\) 更新方案：更新最大值前要保证 \(i\) 、 \(j\) 两点连通。（好傻逼的错误啊）
\(3.\) 点从 \(0\) 开始编号，读入注意。
\(4.\) 所有数组要及时清空，方案数开 \(long\) \(long\) ，路径数为双向所得，要减半。（均没出错）
\(View\) \(Code\)
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int q,n,m,w[13],x,y,f[1<<13][13][13],ans; long long me[1<<13][13][13],answ; bool g[15][15]; inline void pre() { ans=0; answ=0; memset(me,0,sizeof(me)); memset(f,-1,sizeof(f)); for(register int i=0;i<n;i++) { for(register int j=0;j<n;j++) { if(g[i][j]) { f[(1<<i)|(1<<j)][i][j]=w[i]+w[j]+w[i]*w[j]; me[(1<<i)|(1<<j)][i][j]=1; } } } } int main() { q=read(); while(q--) { n=read(); m=read(); for(register int i=0;i<n;i++) w[i]=read(); if(n==1) { printf("%d 1\n",w[0]); continue; } memset(g,0,sizeof(g)); for(register int i=1;i<=m;i++) { x=read(); y=read(); x--; y--; g[x][y]=1; g[y][x]=1; } pre(); for(register int p=0;p<(1<<n);p++) { for(register int i=0;i<n;i++) { if(p&(1<<i)) { for(register int j=0;j<n;j++) { if(p&(1<<j)) { if(g[i][j]&&f[p][i][j]!=-1) { for(register int k=0;k<n;k++) { if(g[j][k]&&i!=k&&!(p&(1<<k))) { int tmp=f[p][i][j]+w[k]+w[j]*w[k]; if(g[i][k]) tmp+=w[i]*w[j]*w[k]; if(f[p|(1<<k)][j][k]<tmp) { f[p|(1<<k)][j][k]=tmp; me[p|(1<<k)][j][k]=me[p][i][j]; } else if(f[p|(1<<k)][j][k]==tmp) me[p|(1<<k)][j][k]+=me[p][i][j]; } } } } } } } } for(register int i=0;i<n;i++) { for(register int j=0;j<n;j++) { if(g[i][j]) { if(f[(1<<n)-1][i][j]>ans) { ans=f[(1<<n)-1][i][j]; answ=me[(1<<n)-1][i][j]; } else if(f[(1<<n)-1][i][j]==ans) answ+=me[(1<<n)-1][i][j]; } } } printf("%d %lld\n",ans,answ/2); } return 0; }转载于:https://www.cnblogs.com/Peter0701/p/11215607.html
相关资源：JAVA上百实例源码以及开源项目