hdu 1016 Prime Ring Problem

dfs水题

#include<iostream>
#include<cstring>
#define maxn 20+5 
#define pr 100000
using namespace std;
int n;
int visit[maxn];
int re[maxn];
int ans;
int u[pr]={0};
void prime()
{
	int i,j;
	u[0]=1,u[1]=1;
	for(i=2;i<pr;i++)
	{
		if(!u[i])
		{
			for(j=2;i*j<pr;j++){u[i*j]=1;}
		}
	}
} 
void dfs(int sum)
{
	if(sum==n&&!u[re[sum-1]+re[0]])
	{
		cout<<re[0];
		for(int i=1;i<n;i++) cout<<' '<<re[i];
		cout<<endl;
	}
	for(int i=1;i<=n;i++)
	{
		if(!visit[i]&&!u[i+re[sum-1]])
		{
			re[sum]=i;visit[i]=1;dfs(sum+1);visit[i]=0;
		}
	}
}
int main()
{
	int casee=1;
	prime();
	while(cin>>n)
	{
		cout<<"Case "<<casee++<<":"<<endl;
		memset(visit,0,sizeof(visit));
		memset(re,0,sizeof(re));
		re[0]=1;
		visit[1]=1;
		dfs(1);
		cout<<endl;
	}
	return 0;
}

hdu 1016 Prime Ring Problem

原文：http://blog.csdn.net/zafkiel_nightmare/article/details/45602257