HDU3091 Necklace 【状压】

题意：有许多珠子，能和别的相邻，求哈密顿回路的方案数

思路：n不大，考虑状压DP，dp[s][i],表示到s状态时，i在最后一个。从任意一个点开始，递推到s包含所有点，最后答案累加时，判断结尾和你选定的起点是否相连

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<list>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
#include<numeric>
#include<functional>
using namespace std;
typedef long long ll;
const int maxn = 1<<20;
ll dp[maxn][19];
int dis[20][20];
int main(void)
{
	int n,m,i,j;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(dis,0,sizeof dis);
		while(m--)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			dis[a][b] = dis[b][a] = 1;
		}
		memset(dp,0,sizeof dp);
		dp[1][1] = 1;
		int en = (1<<n)-1;
		for(int s = 1; s < en; s++)
		{
			for(j = 1; j <= n; j++)
			{
				if(!dp[s][j]) continue;
				for(i = 1; i <= n; i++) // new point
				{
					if(s&(1<<(i-1))) continue;
					if(!dis[i][j]) continue;
					dp[ s|(1<<(i-1)) ][i] += dp[s][j];
				}
			}
		}
		ll ans = 0;
		for(i = 1; i <= n; i++)
		{
			if( dis[i][1] )
				ans += dp[en][i];
		}
		printf("%lldn",ans);
	}
	return 0;
}

最后

以上就是坚定招牌为你收集整理的HDU3091 Necklace 【状压】的全部内容，希望文章能够帮你解决HDU3091 Necklace 【状压】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。