嗯...

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1016

 

一道很典型的dfs+回溯：

根据题意首先进行初始化，即第一个位置为1，然后进行dfs，枚举2~n之间的每一个数，如果这个数没被使用并且它和环中上一个数形成素数环，那么就把它加入环中，打上标记，然后继续dfs，最后回溯。当环上的个数正好等于n并且第一个数和最后一个数也能组成素数，则输出，输出时注意格式，很严格！

 

dfs这里还有一个剪枝：

只有n为偶数时才可能形成素数环！因为当n为奇数时，在1~n中奇数的个数比偶数多一，所以一定会形成两个奇数相邻，则构不成素数....

 

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4  5 using namespace std; 6  7 int n, ring[25], vis[25]; 8  9 inline bool is_prime(int x){10     for(int i = 2; i * i <= x; i++){11         if(x % i == 0) return 0;12     }13     return 1;14 }15 16 inline void dfs(int x){17     if(x == n && is_prime(ring[x] + ring[1])){18         for(int i = 1; i < n; i++)19             printf("%d ", ring[i]);//输出格式要严格 20         printf("%d\n", ring[n]);21         return;22     }23     for(int i = 2; i <= n; i++){24         if(!vis[i] && is_prime(ring[x] + i)){25             vis[i] = 1;26             ring[x + 1] = i;27             dfs(x + 1);28             vis[i] = 0;29         }30     }31 }32 33 int main(){34     int k = 1;35     while(~scanf("%d", &n)){36         memset(ring, 0, sizeof(ring));37         memset(vis, 0, sizeof(vis));38         ring[1] = 1;39         printf("Case %d:\n", k);40         k++;41         if(n % 2 == 0 && n > 0) dfs(1);42         printf("\n");43     }44     return 0;45 }