这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目传送门: http://acm.hdu.edu.cn/showproblem.php?pid=1016
分析:这是素数环的问题,素数环是标准的DFS问题。 直接用next_permutaion()测试会超时。 这里使用回溯法。 这里有一篇在网上看到的对DFS的理解的文章,和大家分享下: http://www.cppleyuan.com/redirect.php?tid=2683&goto;=lastpost#lastpost 解答报告: 根据本题总结dfs的主要步骤和方法: 1. 找搜索出口条件,即搜索到最深层时的操作 2. Dfs采用递归搜索,在遍历后返回时标记已经遍历的节点 3. 注意入口条件的满足 4. 画出递归搜索图查看函数是否满足要求
#include
using namespace std;
int p[40], vis[20],result[20];
int n;
void DFS(int begin, int num) // begin表示前一个字母,num表示后一个字母
{
int i, j;
if(num == n && p[result[1]+result[num]]) //递归边界。注意测试第一个数和最后一个数
{
for(i=1; i<=n; ++i) //打印方案
printf(i==1?"%d":" %d", result[i]);
printf("\n");
return;
}
for(i=2; i<=n; ++i) //尝试放置每一个数i
if(p[begin+i] && vis[i] == 0)
{
result[num+1] = i;
vis[i] = 1;
DFS(i, num+1);
vis[i] = 0;
}
}
int main()
{
p[2] = p[3] = p[5] = p[7] = p[11] = p[13] = p[17]
= p[19] = p[23] = p[29] = p[31] = p[37] = 1;
int i, nCases = 1;
while(scanf("%d", &n;) != EOF)
{
printf("Case %d:\n", nCases++);
result[1] = 1;
if(n%2 == 0)
DFS(1, 1);
printf("\n");
memset(vis, 0, sizeof(vis));
}
return 0;
}