HDU 1016 素数环（dfs + 回溯）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 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 }