1.N皇后问题

2.油田问题

3.素数环问题

4.马踏棋盘问题

5.图的m着色问题

6.01背包问题

7.TSP问题

【Code-1:输出N皇后方案和个数】

#include
    
     using namespace std;typedef long long  ll;const int maxn = 105;const ll INF = 2147483647;typedef pair
     
       pli;int a[maxn],b[maxn],c[maxn],mp[maxn][maxn];int n,cnt;void print(){    for(int i=1;i<=n;i++){        for(int j=1;j<=n;j++)            printf("%d ",mp[i][j]);        printf("\n");    }}int dfs(int i){    for(int j=1;j<=n;j++)    {        if(!a[j] && !b[i-j+n] && !c[i+j])        {            mp[i][j]=i;            a[j]=b[i-j+n]=c[i+j]=1;            if(i==n)            {                print();                printf("\n");                cnt++;            }            else            {                dfs(i+1);            }            mp[i][j]=0;            a[j]=b[i-j+n]=c[i+j]=0;        }    }}int main(){    scanf("%d",&n);    dfs(1);    printf("%d\n",cnt);}
     
    

【HDU-2553-N皇后输出方案数/预处理打表】:

#include
    
     using namespace std;typedef long long  ll;const int maxn = 105;const ll INF = 2147483647;typedef pair
     
       pli;int a[maxn];int cnt=0;int vis[3][maxn];int n;void dfs(int i){    if(i==n+1)    {        cnt++;        return ;    }    for(int j=1;j<=n;j++)    {        if(!vis[0][i-j+n] && !vis[1][j] && !vis[2][i+j])        {            vis[0][i-j+n] = vis[1][j] = vis[2][i+j] = 1;            dfs(i+1);            vis[0][i-j+n] = vis[1][j] = vis[2][i+j] = 0;        }    }}int main(){    for(n=1;n<=10;n++)    {        memset(vis,0,sizeof(vis));        cnt=0;        dfs(1);        a[n]=cnt;    }    while(~scanf("%d",&n),n)    {        printf("%d\n",a[n]);    }}
     
    

【Code-2】：

#include
    
     using namespace std;typedef long long  ll;const int maxn = 105;const ll INF = 2147483647;typedef pair
     
       pli;//int dir[8][2]={ {0,1},{1,-1},{-1,0},{-1,-1},{-1,0},{-1,1},{0,1},{1,1} };int dir[8][2]={1,0,-1,0,0,1,0,-1,1,1,-1,-1,1,-1,-1,1};char mp[maxn][maxn];int n,m;int ok(int x,int y){    if(x>=0 && y>=0 && x
     
    

【Code-3-素数环】：

#include
    
     using namespace std;typedef long long  ll;const int maxn = 105;const ll INF = 2147483647;typedef pair
     
       pli;int n,cnt;int vis[maxn];bool isp(int n){    if(n<=1) return 0;    else    {        for(int i=2;i<=sqrt(n);i++)        {            if(n%i==0) return 0;        }    }    return 1;}int a[maxn];/*int print(){    cnt++;    //printf("(%d)\n",cnt);    for(int j=1;j<=n;j++)        printf("%d ",a[j]);    printf("\n");}*/void dfs(int cur){    if(cur>n && isp(a[1]+a[n]))    {        cnt++;        for(int i=1;i<=n;i++)            printf("%d ",a[i]);        printf("\n");    }    else    {        for(int i=1;i<=n;i++)        {            if(vis[i]==0 && isp(i+a[cur-1]))            {                a[cur]=i;                vis[i]=1;                dfs(cur+1);                vis[i]=0;            }        }    }}int main(){    scanf("%d",&n);    memset(a,0,sizeof(a));    dfs(1);    printf("Total sum is %d\n",cnt);}
     
    

【Code-4-骑士周游】：

#include
    
     using namespace std;typedef long long  ll;const int maxn = 50;const ll INF = 2147483647;typedef pair
     
       pli;int n,m;int cnt;int vis[maxn][maxn];int fx[8]={-1,1,-2,2,-2,2,-1,1};int fy[8]={-2,-2,-1,-1,1,1,2,2};int a[maxn][maxn];int f=0;struct node{    int x,y;    node(int a=0,int b=0):x(a),y(b){}}path[maxn];int ok(int x,int y){    if(x>=1 && y>=1 && x<=n && y<=m && !vis[x][y] && !f)        return 1;    return 0;}void print(){    for(int i=1;i<=n*m;i++){            int x=path[i].x;            int y=path[i].y;            printf("%d %d\n",y,x); //输出坐标        }}void dfs(int x, int y, int d){    path[d]=node(x,y);    if(d==n*m)    {        f=1;        return ;    }    for(int i=0;i<8;i++)    {        int xx=x+fx[i];        int yy=y+fy[i];        if(ok(xx,yy))        {            vis[xx][yy]=1;            dfs(xx,yy,d+1);            vis[xx][yy]=0;        }    }}int main(){    f=0;    memset(vis,0,sizeof(vis));    scanf("%d%d",&n,&m);    vis[1][1]=1;    dfs(1,1,1);    if(!f) puts("No");    else print();}
     
    

【Code-5：洛谷-图的m着色问题】

#include
    
     using namespace std;typedef long long  ll;const int maxn = 50;const ll INF = 2147483647;typedef pair
     
       pli;int n,m;int a[maxn][maxn],c[maxn];int sum=0;int ok(int i){    for(int j=1;j<=n;j++)    {        if(a[i][j] && c[i]==c[j])            return 0;    }    return 1;}void dfs(int cur){    if(cur==n+1)    {        sum++;        for(int i=1;i<=n;i++)            printf("%d ",c[i]);        printf("\n");        return ;    }    else    {        for(int i=1;i<=m;i++)        {            c[cur]=i;            if(ok(cur))            {                dfs(cur+1);            }            c[cur]=0;        }    }}int main(){    int x,y,k;    scanf("%d%d%d",&n,&k,&m);    while(k--)    {        scanf("%d%d",&x,&y);        a[x][y]=a[y][x]=1;    }    dfs(1);    if(!sum) puts("No");    else printf("%d\n",sum);}/*5 8 41 21 31 42 32 42 53 44 548*/
     
    

【Code6-01背包回溯版】：

#include
    
     using namespace std;typedef long long  ll;const int maxn = 2*1e5+5;const ll INF = 2147483647;typedef pair
     
       pli;//int v[maxn],w[maxn];int n,c,cp,bestp;//物品数、背包大小、当前价值、最优价值int x[maxn],bestx[maxn];//当前解、最优解struct node{    int v,w;//价值、重量}a[maxn];bool cmp(node a, node b){    return a.v*b.w > b.v*a.w;}void print(){    for(int i=0;i
      
       =n)    {        if(bestp
      
     
    

【输出路径版】

#include
    
     using namespace std;typedef long long  ll;const int maxn = 2*1e5+5;const ll INF = 2147483647;typedef pair
     
       pli;int w[maxn];  int v[maxn];  int best_ans[maxn], ans[maxn];  int cw, cv, n, max_w, max_v ;void print()  {      printf("%d\n",max_v);      for(int i=0;i
      
       =n)      {          if(cv > max_v)          {               max_v = cv;            for(int i=0;i
       
        = w[step])          {               ans[step] = 1;  cv += v[step]; cw -= w[step];              DFS(step+1,cw,cv);              ans[step] = 0;  cv -= v[step]; cw += w[step];         }          ans[step]=0;        DFS(step+1,cw,cv);      }  }    void init()  {      max_v = 0;      for(int i=0;i