P1171 售货员的难题

题目背景

数据有更改

题目描述

某乡有n个村庄(1<n<20)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0<s<1000)是已知的，且A村到B村与B村到A村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为1，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。

输入输出格式

输入格式：

村庄数n和各村之间的路程(均是整数)。

输出格式：

最短的路程。

输入输出样例

输入样例#1：

输出样例#1：

说明

输入解释

3 {村庄数}

0 2 1 {村庄1到各村的路程}

1 0 2 {村庄2到各村的路程}

2 1 0 {村庄3到各村的路程}

80分的暴力：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,tot;

int vis[];

int map[][];

int minn=0x7f7f7f7f,ans=0x7f7f7f7f;

void dfs(int now,int num,int dis){

    if(num==n){

        ans=min(ans,dis+map[now][]);

        return ;

    }

    if(dis+n-num-+minn>=ans)    return ;

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

        if(!vis[i]){

            vis[i]=;

            dfs(i,num+,dis+map[now][i]);

            vis[i]=;

        }

}

int main(){

    scanf("%d",&n);

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

        for(int j=;j<=n;j++)

            scanf("%d",&map[i][j]);

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

        minn=min(minn,map[i][]);

    vis[]=;

    dfs(,,);

    cout<<ans;

}

/*

3

0 1 2

2 0 1

1 2 0

*/

正解：

状压的思路是一样的。用 f [ i ] [ j ] 来表示 i 状态下走到第 j 个地方的最小值。这里的 i 实质上是一个二进制数，每一位是 0 是 1 即表示每个地方有无去过，但是转为十进制表示状态，这便是状态压缩的基本思想。先从 3（二进制 11）枚举 i，每次给 i 加 2（因为第一位所表示的第一个地方是起点，不管如何都去过，因此其永远是 1）。得到可能的 i 后，枚举 i 的除第一位外每个为 1 的位，并替换 1 为 0 得到能转移到状态 i 的状态 s，具体转移过程就不多说了，总之位运算什么的详见代码。

那么如何进行优化呢？下面就是几个好办法：

1 . 首先如果规定 n = 5，即有售货员要去五个地方，枚举到 i = 3（二进制 00011）时，我们不一定需要从最低位一直枚举到第 n 位，因为第 n 位可能在枚举 i 的很久以后才能变成 1，这之前都是 0，浪费时间复杂度，因此我们可以规定整数 k，表示目前可能为 1 的最高位的位数。当 i 超过 2 的 k 次方时，更新 k，即为 k 自增。这里 2 的 k 次方可以暂时用变量 p 表示，k 更新时用位运算给 p 向左移一位。
2 . 尽量不用 STL 的 min，虽然好用，但是宁愿用 define 手打 QAQ，另外其他联系到位运算的，比如取某数二进制位下的某位的值，也可以用 define 而不是新建什么内联函数。
3 . 对于状态 i，其由不同的状态 s 转移而来，因此，我们倒推 s 的时候，先确认其可行性，再枚举 l ，用 f [ s ] [ l ] 更新 f [ i ] [ j ] 的最小值。

个人认为第 2 点优化程度是最大的。下面给出代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define min(a,b)    a<b?a:b

using namespace std;

int n,m,ans=0x7f7f7f7f;

int map[][],f[<<][];

int main(){

    scanf("%d",&n);

    m=(<<n)-;

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

        for(int j=;j<=n;j++)

            scanf("%d",&map[i][j]);

    memset(f,0x7f,sizeof(f));

    f[][]=;

    for(int i=,k=,p=;i<=m;i+=){

        if(i>p)    p=p<<,k++;

        for(int j=;j<=k;j++)

            if((i>>j-)&){

                int s=i^(<<j-);

                for(int l=;l<j;l++)

                    f[i][j]=min(f[i][j],f[s][l]+map[l][j]);

                for(int l=j+;l<=k;l++)

                    f[i][j]=min(f[i][j],f[s][l]+map[l][j]);

            }

    }

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

        ans=min(ans,f[m][i]+map[i][]);

    cout<<ans;

}

售货

洛谷 P1171 售货员的难题

P1171 售货员的难题

题目背景

题目描述

输入输出格式

输入输出样例

说明