OI

【搜索】枚举全排列

P1433吃奶酪
搜索走的路径是一个1~n的全排列，再加上简单剪枝（当前路径长度超过已知最短就剪掉）即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<stdio.h>
#include<math.h>
#define inf 2147483647
struct node{
    double x,y;
};
struct node a[20];
int n;
double map[20][20]={0};
double dist(int x,int y){
    return sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));
}

int ord[20]={0},visited[20]={0};
double ans=0,min=inf;

void dfs(int i){
    if(ans>min)return;
    int j;
    for(j=1;j<=n;j++)
      if(!visited[j]){
          ord[i]=j;
          visited[j]=1;
          ans+=map[ord[i-1]][j];
          if(i==n&&ans<min)min=ans;
          else dfs(i+1);
          ans-=map[ord[i-1]][j];
          ord[i]=0;
          visited[j]=0;
      }
}

int main(){
    int i,j;
    scanf("%d",&n);
    a[0].x=0;
    a[0].y=0;
    for(i=1;i<=n;i++){
        scanf("%lf%lf",&a[i].x,&a[i].y);
        for(j=0;j<i;j++){
          map[i][j]=dist(i,j);
          map[j][i]=map[i][j];
        }
    }
    dfs(1);
    printf("%.2lf",min);
    return 0;
}

P1118
原理也是枚举全排列，系数是杨辉三角（可耻地打了表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<stdio.h>
int a[20][20]={{1,1},
               {0,1},
               {0,1,2,1},
               {0,1,3,3,1},
               {0,1,4,6,4,1},
               {0,1,5,10,10,5,1},
               {0,1,6,15,20,15,6,1},
               {0,1,7,21,35,35,21,7,1},
               {0,1,8,28,56,70,56,28,8,1},
               {0,1,9,36,84,126,126,84,36,9,1},
               {0,1,10,45,120,210,252,210,120,45,10,1},
               {0,1,11,55,165,330,462,462,330,165,55,11,1},
               {0,1,12,66,220,495,792,924,792,495,220,66,12,1}
};
int n,f=0,max,sum=0,visited[20]={0},ord[20]={0};

void pr(){
    int i;
    for(i=1;i<=n;i++)
      printf("%d ",ord[i]);
    //printf("s%d\n",sum);
}

void dfs(int i){
    if(f||sum>max)return;
    int j;
    for(j=1;j<=n;j++)
      if(!visited[j]){
          visited[j]=1;
          ord[i]=j;
          sum+=a[n-1][i]*j;
          if(i==n&&sum==max){
            pr();
            f=1;
          }
          else dfs(i+1);
          sum-=a[n-1][i]*j;
          visited[j]=0;
          ord[i]=0;
      }
}

int main(){
    int i,j;
    scanf("%d%d",&n,&max);
    dfs(1);
    
    return 0;
}