[关闭]
@ysner 2018-09-18T20:16:47.000000Z 字数 2091 阅读 2152

[noip2017]宝藏

DP 状压DP


题面

戳我

解析

这确实是一道搜索可以过的题。。。
一般的暴力,就是枚举出发点,记录下当前已到过哪些点,以及每个点的深度(值),然后对每个状态枚举走的下一条路的起点和终点。
当然,最优性剪枝谁都会。

这样复杂度。可以获得

然而我们可以再加剪枝。
对于出发点相同的同一状态,如果当前到达当前状态的费用比以前的大,就可以停止搜索。
这样就可以。。。

显然这个剪枝是有问题的,因为后面的结果还受当前状态中每个点的深度的影响。也可能当前不优,最后能最优呢。

给一组数据一下。(来自洛谷讨论版
正确答案。我的代码去掉剪枝是,加上剪枝
我原来的代码

  1. il void upd(re int &x,re int y){x=x<y?x:y;}
  2. il void dfs(re int tag,re int sum)
  3. {
  4. if(sum>=ans) return;
  5. if(tag==(1<<n)-1) {upd(ans,sum);return;}
  6. fp(s,1,n)
  7. if(d[s])
  8. fp(t,1,n)
  9. if(!d[t]&&mp[s][t]!=inf)
  10. {
  11. re int nxt=tag|(1<<t-1),res=sum+d[s]*mp[s][t];
  12. if(f[nxt]>res)//剪枝
  13. {
  14. d[t]=d[s]+1;
  15. f[nxt]=res;
  16. dfs(nxt,res);
  17. d[t]=0;
  18. }
  19. }
  20. }
  21. int main()
  22. {
  23. n=gi();m=gi();
  24. fp(i,0,19) fp(j,0,19) mp[i][j]=inf;
  25. fp(i,1,m)
  26. {
  27. re int u=gi(),v=gi(),w=gi();
  28. mp[u][v]=mp[v][u]=min(mp[u][v],w);
  29. }
  30. fp(i,1,n)
  31. {
  32. memset(d,0,sizeof(d));memset(f,63,sizeof(f));
  33. d[i]=1;f[1<<i-1]=0;
  34. dfs(1<<i-1,0);
  35. }
  36. printf("%d\n",ans);
  37. return 0;
  38. }

下面来谈一谈有理有据的算法。
用二进制表示结点集合,设表示点在当时可走点的集合为的情况下,下一步走的距离最小是多少。
此时点深度也是确定的,所以也能保证答案最小。

再设表示当前加入深度为的点,此时已加入点集合为的最小代价。
然后按照深度依次更新值,就没有后效性的问题了。
具体来说,是先枚举深度,再枚举加完点后的集合,再枚举其子集(即加点前的集合)。最后在加点前的集合中枚举出发点,以统计的和。

复杂度
所以这题应该放的。。。

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cmath>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define max(a,b) (((a)>(b))?(a):(b))
  11. #define min(a,b) (((a)<(b))?(a):(b))
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. const int N=13,inf=5e6;
  16. int n,m,all,dis[N][N],f[N][1<<N],dp[N][1<<N],s;
  17. il ll gi()
  18. {
  19. re ll x=0,t=1;
  20. re char ch=getchar();
  21. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  22. if(ch=='-') t=-1,ch=getchar();
  23. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  24. return x*t;
  25. }
  26. int main()
  27. {
  28. n=gi();m=gi();all=(1<<n)-1;
  29. fp(i,0,12) fp(j,0,12) dis[i][j]=inf;
  30. fp(i,0,12) fp(j,0,(1<<N)-1) f[i][j]=dp[i][j]=inf;
  31. fp(i,1,m)
  32. {
  33. re int u=gi(),v=gi(),w=gi();
  34. dis[u][v]=dis[v][u]=min(dis[u][v],w);
  35. }
  36. fp(i,1,n)
  37. fp(j,0,all)
  38. fp(k,1,n)
  39. if((j>>k-1)&1) f[i][j]=min(f[i][j],dis[i][k]);
  40. fp(i,1,n) dp[1][1<<i-1]=0;
  41. fp(i,2,n)
  42. fp(j,0,all)
  43. for(re int k=j;k;k=(k-1)&j)
  44. {
  45. s=0;
  46. fp(l,1,n)
  47. if(((j^k)>>l-1)&1) s+=f[l][k];
  48. dp[i][j]=min(dp[i][j],dp[i-1][k]+s*(i-1));
  49. }
  50. printf("%d\n",dp[n][all]);
  51. return 0;
  52. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注