[HDU 1016]--Prime Ring Problem(回溯)

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

Prime Ring Problem

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Problem Description

A ring is compose of n circles as shown in diagram. Put
natural number 1, 2, ..., n into each circle separately, and the sum of numbers
in two adjacent circles should be a prime.

Note: the number of first
circle should always be 1.

Input

n (0 < n < 20).

Output

The output format is shown as sample below. Each row
represents a series of circle numbers in the ring beginning from 1 clockwisely
and anticlockwisely. The order of numbers must satisfy the above requirements.
Print solutions in lexicographical order.

You are to write a program that
completes above process.

Print a blank line after each case.

Sample Input

Sample Output

Case 1:

1 4 3 2 5 6

1 6 5 2 3 4

Case 2:

1 2 3 8 5 6 7 4

1 2 5 8 3 4 7 6

1 4 7 6 5 8 3 2

1 6 7 4 3 8 5 2

Source

Asia
1996, Shanghai (Mainland China)

Recommend

JGShining | We have carefully selected several
similar problems for you: 1010 1241 1312 1072 1242

题目大意：有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。

　　　　　为了简便起见，我们规定每个素数环都从1开始。有多组测试数据，每组输入一个n(0<n<20)，n=0表示输入结束。

　　　　　输出每组第一行输出对应的Case序号，从1开始。如果存在满足题意叙述的素数环，从小到大输出。

解题思路：回溯的思想就是了，一个dfs搞定，最坑爹的是，每输完一组末尾都要加上换行，我没加结果提交wa,明明是pe,各种改,

　　　　　彻底无爱了，Orz~~~

代码如下：

 #include <iostream>

 #include <cstring>

 using namespace std;

 #define maxn 40

 int vis[], x[], T, n;

 int prime[maxn] = { , ,  };

 void init()

 {

     int i, j;

     for (i = ; i <= maxn; i++){

         if (!prime[i]){

             for (j = ; i*j <= maxn; j++)

                 prime[i*j] = ;

         }

     }

 }

 void dfs(int cur){

     if (cur == n&&!prime[ + x[n - ]]){

         for (int i = ; i < n; i++){

             if (i) cout << ' ';

             cout << x[i];

         }

         cout << endl;

     }

     else for (int i = ; i <= n; i++){

         if (!vis[i] && !prime[i + x[cur - ]]){

             x[cur] = i;

             vis[i] = ;

             dfs(cur + );

             vis[i] = ;

         }

     }

 }

 int main(){

     init();

     while (cin >> n){

         cout << "Case " << ++T << ':' << endl;

         if (n == )

             cout <<  << endl;

         else if (n & )

             cout << endl;

         else{

             memset(vis, , sizeof(vis));

             x[] = ;

             dfs();

         }

         cout << endl;//没加这一句pe来个wa,我也是醉了,各种改,无爱了~~~~

     }

     return ;

 }

巴特西

[HDU 1016]--Prime Ring Problem(回溯)

最新文章

热门文章