自动搬运

查看原文

来自洛谷，原作者为

	meifan666 We have the power to face the future.

搬运于2025-08-24 23:02:59，当前版本为作者最后更新于2025-07-23 15:10:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定一张有 $n$ 个点和 $m$ 条边的无向图，求最佳三角形哈密顿路径的最大值（计算方法不再赘述），并求出最优解的种类数。

思路

题目让我们求的是特殊哈密顿路径，加之 $n\le13$ 的条件，不难想到状压 dp。

对于第一问，我们发现要想计算路径的值，就一定得知道连续三个点的联通情况，于是我们令 $dp[i][j][k]$ 表示二进制状态（即走过的点）为 $i$，现在在 $j$ 点，上一步在 $k$ 点，此时的最大值。dp 时考虑点的联通情况并按题目条件模拟即可（具体的状态转移方程见代码）。

对于第二问，很容易想到类比最短路计数这题的思想，令 $sum[i][j][k]$表示二进制状态为 $i$，现在在 $j$ 点，上一步在 $k$ 点，最优解的数量，同 dp 数组一起变化。同时要注意的是，如果一条路径的顺序反转，仍认为它是相同的路径，所以要将结果除以 $2$，因为对于每一条路径，重复了且只重复算了 $1$ 次它的反转形式。

下面贴上代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int T,n,m,dp[1<<14][15][15],sum[1<<14][15][15],v[15],x,y;
int ans1,ans2;
bool edge[15][15];
void init(){
	ans1=0,ans2=0;
	memset(edge,0,sizeof(edge));
	memset(dp,-0x3f,sizeof(dp));
	memset(sum,0,sizeof(sum));
} 
signed main(){
	cin>>T;
	while(T--){
		cin>>n>>m;init();
		for(int i=0;i<n;i++){
			cin>>v[i];
		}
		if(n==1){cout<<v[0]<<' '<<1<<'\n';continue;}
		while(m--){
			cin>>x>>y;--x,--y;
			edge[x][y]=edge[y][x]=1;
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(!edge[i][j])continue;
				dp[(1<<i)|(1<<j)][i][j]=v[i]+v[j]+v[i]*v[j];
				sum[(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)continue;
				for(int k=0;k<n;k++){
					if((i&(1<<k))==0||!edge[k][j]||j==k)continue;
					for(int l=0;l<n;l++){
						if((i&(1<<l))==0||!edge[k][l]||j==l||k==l)continue;
						int t=dp[i^(1<<j)][k][l];
						t+=v[k]*v[j]+v[j];
						if(edge[l][j])t+=v[j]*v[k]*v[l];
						if(t>dp[i][j][k])
							dp[i][j][k]=t,sum[i][j][k]=sum[i^(1<<j)][k][l];
						else if(t==dp[i][j][k])
							sum[i][j][k]+=sum[i^(1<<j)][k][l];
					}
				}
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(i==j)continue;
				if(dp[(1<<n)-1][i][j]>ans1)
					ans1=dp[(1<<n)-1][i][j],ans2=sum[(1<<n)-1][i][j];
				else if(dp[(1<<n)-1][i][j]==ans1)
					ans2+=sum[(1<<n)-1][i][j];
			}
		}
		cout<<ans1<<' '<<ans2/2<<'\n';
	}
	return 0;
}

最后要注意，如果你错在第 $4$ 个点，记住特判 $n=1$ 的情况。