题解 Luogu P3959 【宝藏】
程序员文章站
2023-08-22 22:16:54
来一篇不那么慢的状压??? 话说这题根本没有紫题难度吧,数据还那么水 我是不会告诉你我被hack了 一看数据规模,n≤12,果断状压。 然后起点要枚举,就设dp状态: 其中j是一个二进制数(用十进制来表示)第i位的1、0分别表示是否已经到达第i点(1表示已经到达,0表示还未到达) (因为m很大,n很 ......
来一篇不那么慢的状压???
话说这题根本没有紫题难度吧,数据还那么水
我是不会告诉你我被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;
}
上一篇: 荣耀20S同台新品已入网 赵明:另一档位王者很吓人的
下一篇: C#通过域名获得IP地址的方法
推荐阅读
-
题解 Luogu P3959 【宝藏】
-
Luogu - P1018 乘积最大 - 题解
-
Luogu CSP 2020 第一轮(初赛)模拟 题解&总结
-
luogu-P1618 三连击(升级版)【STL next_permutation()】【看题解啊】【二刷呀】
-
【题解】Luogu P1204 [USACO1.2]挤牛奶Milking Cows
-
【题解】LuoGu6859:蝴蝶与花
-
题解 Luogu P1099 【树网的核】
-
[luogu2048] [bzoj2006] [NOI2010] 超级钢琴 题解
-
【题解】Luogu1739 表达式括号匹配
-
Luogu - P1018 乘积最大 - 题解