NOIP2017 D2T2 宝藏

洛谷P3959

其实就是一道暴力搜索题……只是需要一个状态压缩的剪枝比较难想而已

这根本不叫dfs！只是一个递归而已……开始就被dfs坑了

思路：

首先一个基本的预处理

数据范围n≤12,m≤5000，说明肯定有很多没用的边，在读入的时候预处理掉就可以了，另外n很小可以用邻接矩阵存图访问快

解法一：暴力搜索

直接暴力搜索，开一个数组记录一个点有没有被访问过。每到一个状态，从访问过的点到未访问过的点引边算代价，递归枚举一下即可。但此方法时间复杂度较大，大约为O(n^n)?（没有仔细算），n<=8差不多能过

期望得分：70分（然而实际得分只有60分）

解法二：状态压缩剪枝

解法一很显然有很多无用的操作，那么如何进行剪枝呢？

答案是：状态压缩（这也是博主第一次接触到这个）

状态压缩就是用一个01串表示一个状态

每一位0代表未选择，1代表被选择

实际操作中我们通常用二进制数来表示状态压缩，为了方便我们用倒序（最右边是第一个，紧挨着是第二个，以此类推）

比如01串010001就可以表示第1个、第5个元素被选择了

然后使用位运算加速

选择某个元素（加入状态）：x=x|(1<<(i-1))

判断第i个元素有没有选择：x&(1<<(i-1))（真：被选择；假：未选择）

那么，开一个数组f[i]表示当前根节点下状态为i的已搜索到的最小代价

这样我们在搜索时，如果这一次更新的代价比当前状态下以搜索到的最小代价要大（更新的代价>f[i]），说明这次搜索一定不是最优解，就不用进行递归算到最后

剪枝到底能减掉多少我不知道……但这一题可以AC了

期望得分：100分

AC代码：

 #include<cstdio>

 #include<climits>

 #include<cstring>

 using namespace std;

 int f[];//状态压缩答案存储

 int tu[][];//邻接矩阵存图

 int n,m;//点、边数

 int depth[];//每个点深度

 void find(int x)

 {

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

         if(x&(<<(i-)))//编号为i的点访问过，从它开始更新

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

                 if((!(x&(<<(j-))))&&tu[i][j]!=INT_MAX)//编号为j的点未访问过且i，j间有边相连

                     if(f[x]+depth[i]*tu[i][j]<f[x|(<<(j-))])//连i,j后答案比之前找出答案小则继续寻找，否则一定不是最优解，不用递归

                     {

                         f[x|(<<(j-))]=f[x]+depth[i]*tu[i][j];

                         depth[j]=depth[i]+;

                         find(x|(<<(j-)));

                     }

 }

 int min(int a,int b){return a<b?a:b;}

 int main()

 {

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

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

             tu[i][j]=INT_MAX;

     scanf("%d%d",&n,&m);

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

     {

         int u,v,w;

         scanf("%d%d%d",&u,&v,&w);

         tu[u][v]=tu[v][u]=min(tu[u][v],w);//存最小边

     }

     int ans=INT_MAX;//保存答案

     for(int i=;i<=n;i++)//对每个点暴力枚举

     {

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

             f[j]=INT_MAX;//每一个根节点都要初始化f[]

         f[<<(i-)]=;

         depth[i]=;//根节点深度为1

         find(<<(i-));

         ans=min(ans,f[(<<n)-]);

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

NOIP2017 D2T2 宝藏

思路：

解法一：暴力搜索

解法二：状态压缩剪枝

最新文章

热门文章