本来想好到csp之前就不写题解了
结果看了篇题解——
这个神仙解法我吹爆！
如果觉得我的解释不够清晰，可以看这篇博客
蒟蒻只会dfs
参考这位的70分做法
(w_{i,j})读入的时候就要存好
用vis数组保存当前是否访问过，dep保存离根点数+1。
爆搜，爆搜。
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,ans=inf,sum;
bool vis[15];
int dep[15],w[15][15];
void dfs(int step){
if(step==n){
ans=min(ans,sum);
return;
}
if(sum>=ans) return;
for(int i=1;i<=n;i++){
if(vis[i]) continue;//下一个挖开的宝藏屋
for(int j=1;j<=n;j++){
if(i==j||vis[j]==0) continue;//出发点
if(w[i][j]==inf) continue;
sum+=dep[j]*w[i][j];vis[i]=1;dep[i]=dep[j]+1;
dfs(step+1);
sum-=dep[j]*w[i][j];vis[i]=0;dep[i]=0;
}
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
w[i][j]=inf;
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
w[a][b]=w[b][a]=min(w[a][b],c);
}
for(int i=1;i<=n;i++){
vis[i]=1;dep[i]=1;sum=0;
dfs(1);
vis[i]=0;dep[i]=0;
}
printf("%d
",ans);
return 0;
}
n范围极小，状压。
dfs+状压DP
其实就是用dfs来实现状压DP的转移吧
(f_i)表示达到该种情况下最小代价
(dis_i)表示赞助商帮你打通的宝藏屋到第i个宝藏屋所经过的宝藏屋的数量
-
枚举从每个点出发的情况
-
dfs+状压 暴力更新
这个思路简洁明了。
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=15;//这样写代码看着比较舒服
int n,m,ans=inf;
int dis[N],w[N][N],f[1<<N];
void dfs(int s){
for(int i=1;i<=n;i++){
if(s&(1<<(i-1))){//该屋已经被挖开了
for(int j=1;j<=n;j++){
if(!((1<<(j-1))&s)&&w[i][j]!=inf){//该屋没被挖开且可以到达
if(f[s+(1<<(j-1))]>f[s]+w[i][j]*dis[i]){//接下来是更新
int tmp=dis[j];//保存，待会儿要回溯
dis[j]=dis[i]+1;
f[s+(1<<(j-1))]=f[s]+w[i][j]*dis[i];//更新
dfs(s+(1<<(j-1)));
dis[j]=tmp;//回溯
}
}
}
}
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
w[i][j]=inf;
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
w[a][b]=w[b][a]=min(w[a][b],c);//预处理
}
for(int i=1;i<=n;i++) dis[i]=inf;
for(int k=1;k<=n;k++){
for(int i=1;i<=(1<<n)-1;i++)
f[i]=inf;
dis[k]=1;
f[(1<<(k-1))]=0;
dfs(1<<(k-1));
ans=min(ans,f[(1<<n)-1]);
}
printf("%d
",ans);
return 0;
}