题解：P10963 Islands and Bridges

meifan666 · 2025-07-23 15:10:07 · 题解

题目大意

给定一张有

个点和

条边的无向图，求最佳三角形哈密顿路径的最大值（计算方法不再赘述），并求出最优解的种类数。

思路

题目让我们求的是特殊哈密顿路径，加之

的条件，不难想到状压 dp。

对于第一问，我们发现要想计算路径的值，就一定得知道连续三个点的联通情况，于是我们令

表示二进制状态（即走过的点）为

点，上一步在

点，此时的最大值。dp 时考虑点的联通情况并按题目条件模拟即可（具体的状态转移方程见代码）。

对于第二问，很容易想到类比最短路计数这题的思想，令

点，上一步在

点，最优解的数量，同 dp 数组一起变化。同时要注意的是，如果一条路径的顺序反转，仍认为它是相同的路径，所以要将结果除以

次它的反转形式。

下面贴上代码。

#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;
}

最后要注意，如果你错在第

个点，记住特判

的情况。