题意:给你一个数n,代表有从1-n个整数点可供使用,然后你要用这些数围成一个圈圈,保证每两个相邻的数相加为素数。

        思路:DFS,判断后一个与前一个相加为素数,注意最后一个和第一个的特殊情况,把素数打了个表,时间降了一半。


题目:http://acm.hdu.edu.cn/submit.php?pid=1016


代码:


Memory: 1728 KB
Time: 436 MS
Language: C++
Result: Accepted

#include <iostream>
#include <cstdio>
#include <cmath>
#include <memory.h>
using namespace std;
const int maxn=20+5;
int ans[maxn], flag[maxn];
int ss[50];
int n, cas=0;
void dfs(int x, int cnt)
{
    if(cnt>1 && ss[x+ans[cnt-1]]==0)return;        //相邻情况判断
    if(cnt==n && ss[x+ans[1]]==0)return;            //尾部和头部判断
    flag[x]=1;    //标记此数被访问
    ans[cnt]=x;    //放入答案中
    if(cnt==n && ss[x+ans[1]]==1)        //找到案例输出
    {
        for(int k=1;k<=n;k++)
        {
            printf("%d", ans[k]);
            if(k==n)printf("\n");
            else printf(" ");
        }
    }
    for(int j=1;j<=n;j++)        //DSF搜索下一个未被访问的点
    {
        if(!flag[j])
        {
            flag[j]=1;
            dfs(j, cnt+1);
            flag[j]=0;
        }
    }
    return;
}
int main()
{
    memset(ss, 0, sizeof(ss));
    ss[1]=ss[2]=ss[3]=ss[5]=ss[7]=ss[11]=ss[13]=ss[17]=ss[19]=ss[23]=ss[29]=ss[31]=ss[37]=ss[41]=ss[43]=ss[47]=1;//打表
    while(~scanf("%d", &n))
    {
        printf("Case %d:\n", ++cas);
        for(int i=0;i<maxn;i++){ans[i]=0;flag[i]=0;}
        for(int i=1;i<=n;i++)
        {
            dfs(i, 1);
        }
        printf("\n");
    }
    return 0;
}