题解 Luogu P3959 【宝藏】
2019-09-23 08:40:58来源:博客园 阅读 ()
题解 Luogu P3959 【宝藏】
来一篇不那么慢的状压???
话说这题根本没有紫题难度吧,数据还那么水
我是不会告诉你我被hack了
一看数据规模,n≤12,果断状压。
然后起点要枚举,就设dp状态:
f[i][j]=以i为起点到j状态的最小花费
其中j是一个二进制数(用十进制来表示)第i位的1、0分别表示是否已经到达第i点(1表示已经到达,0表示还未到达)
(因为m很大,n很小,会有重边,所以用邻接矩阵(e[u][v]))
由此可以列出状态转移方程:
f[i][j]=min{f[i][k]+diss[i][k][u]*e[u][v]} (j&(1<<(u-1))!=0,j&(1<<(v-1))!=0,i!=v,k=j^(1<<(v-1)),e[u][v]!=1e9)
(e[u][v]!=1e9说的就是u、v之间有边)
什么意思?就是说我们再找一个状态(k)比当前状态(j)只少一个点(显然不能是起点),然后从k向j拓展,在所有的k中取花费最少的那种。
但是还有一个问题,该边的花费怎么算?
根据题目描述,就将该边长度乘上起点到uu经过的点数(dis[i][j][u])即可。
问题又来了,dis[i][j][u]怎么算?
每次状态转移的时候顺便转移一下即可
代码如下:
#include<cstdio> inline int read(){ int r=0,f=1; char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+c-'0',c=getchar(); return r*f; } int n,ans=1e9,m,f[15][5005],e[15][15],dis[15][5005][15]; inline int min(int a,int b){ return a<b?a:b; } int main(){ freopen("treasure.in","r",stdin); freopen("treasure.out","w",stdout); n=read(),m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) e[i][j]=1e9; for(int i=1;i<=m;i++){ int u=read(),v=read(); if(u-v)e[u][v]=e[v][u]=min(e[u][v],read()); } for(int i=1;i<=n;i++) for(int j=1;j<1<<n;j++) f[i][j]=1e9; for(int i=1;i<=n;i++){ f[i][1<<(i-1)]=0; dis[i][1<<(i-1)][i]=1; for(int j=(1<<(i-1))+1;j<1<<n;j++){ if(!(j&(1<<(i-1))))continue; int x=j,u=1; while(x){ if(x&1){ for(int v=1;v<=n;v++){ if(i==v||e[u][v]==1e9||!(j&(1<<(v-1))))continue; int k=j^(1<<(v-1)); if(f[i][j]>f[i][k]+dis[i][k][u]*e[u][v]){ f[i][j]=f[i][k]+dis[i][k][u]*e[u][v]; for(int y=1;y<=n;y++)dis[i][j][y]=dis[i][k][y]; dis[i][j][v]=dis[i][k][u]+1; } } } u++; x>>=1; } } ans=min(ans,f[i][(1<<n)-1]); } printf("%d",ans); return 0; }
原文链接:https://www.cnblogs.com/wyzwyz/p/11542904.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Unsolved --> Solved OJ思路题解 2020-05-30
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- 【题解】Building Strings Gym - 102152E 2020-03-31
- GPLT-天梯赛-题解目录 2020-03-22
- 题解 P5116 【[USACO18DEC]Mixing Milk】 2020-03-14
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash