本文主要是介绍汉密尔顿回路求解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
汉密尔顿通路：给定图G，若存在一条经过图中的每个顶点一次且仅一次的通路，则称这条
通路为汉密尔顿通路。
汉密尔顿回路：若存在一条回路，经过图中的每个顶点一次且仅一次，则
称这条回路为汉密尔顿回路。
汉密尔顿图：具有汉密尔顿回路的图称为汉密尔顿图。
zoj 2398 poj 2288
地图中有许多岛屿 沿着桥访问每个岛屿一次且仅一次的路径
每个岛屿还有相应的权值 根据路径 会有相应的求值方式
求出最大的权值和以及路径的数目
使用二进制位表示路径状态 用状态值记录 权值和路径数
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>#define eps 1e-8
#define op operator
#define MOD 10009
#define MAXN 13
#define INF 0x7fffffff
#define MEM(a,x) memset(a,x,sizeof a)
#define ll long long
#define MAXSTATUS 1<<13//状态最大数目using namespace std;ll dp[MAXSTATUS][MAXN][MAXN];
ll ways[MAXSTATUS][MAXN][MAXN];ll value[MAXN];
bool link[MAXN][MAXN];
int nislands;
ll maxvalue; //最好的三角汉密尔顿回路路径的权值
ll maxways;//最多路径数目void init()
{int nbridges;scanf("%d%d",&nislands,&nbridges);for(int i=0;i<nislands;i++)scanf("%lld",&value[i]);if(nislands==1) return;MEM(dp,-1); MEM(ways,0); MEM(link,0);for(int i=0;i<nbridges;i++){int row,col;scanf("%d%d",&row,&col);row--; col--;link[row][col]=1; link[col][row]=1;dp[(1<<row)|(1<<col)][row][col]=value[row]+value[col]+value[row]*value[col];dp[(1<<row)|(1<<col)][col][row]=value[row]+value[col]+value[row]*value[col];ways[(1<<row)|(1<<col)][row][col]=1;ways[(1<<row)|(1<<col)][col][row]=1;}
}void solve()
{ll tmp;int nextstatus;if(nislands==1){maxvalue=value[0];maxways=1;return;}for(int s=0;s<(1<<nislands);s++){for(int i=0;i<nislands;i++){if(s&(1<<i)){for(int j=0;j<nislands;j++){if(i!=j&&(s&(1<<j))&&dp[s][i][j]>-1){for(int k=0;k<nislands;k++){if(!(s&(1<<k))&&link[i][k]==1){nextstatus=s|(1<<k);tmp=dp[s][i][j]+value[k]+value[i]*value[k];if(link[j][k]==1)tmp+=value[i]*value[j]*value[k];if(dp[nextstatus][k][i]==tmp)ways[nextstatus][k][i]+=ways[s][i][j];else if(dp[nextstatus][k][i]<tmp){dp[nextstatus][k][i]=tmp;ways[nextstatus][k][i]=ways[s][i][j];}}}}}}}}maxvalue=-1;maxways=0;int s=(1<<nislands)-1;for(int i=0;i<nislands;i++){for(int j=0;j<nislands;j++){if(!link[i][j]) continue;if(dp[s][i][j]==maxvalue)maxways+=ways[s][i][j];else if(dp[s][i][j]>maxvalue){maxways=ways[s][i][j];maxvalue=dp[s][i][j];}}}maxways/=2;
}int main()
{
//freopen("ceshi.txt","r",stdin);int tc;scanf("%d",&tc);while(tc--){init();solve();if(maxvalue==-1)printf("0 0\n");elseprintf("%lld %lld\n",maxvalue,maxways);}return 0;
}
这篇关于汉密尔顿回路求解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
