题解 P3959 【宝藏】

看到题解里那么多大佬用一些高级算法，蒟蒻不知什么意思，但蒟蒻有一种比较简单的随机化想法。就是复杂度可能较高。 核心想法如下， ```cpp random_shuffle(s+1,s+1+n); ``` 每次重置一次宝屋的顺序。 以便于得到顺序，统计层数，每到一个点，就选取已开通的且到该屋子最近的点 代码如下 ```cpp #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int INF=0x3f3f3f3f; void read(int &x) { x=0;char a=getchar(); while(a<'0'||a>'9')a=getchar(); while(a>='0'&&a<='9')x=(x<<3)+(x<<1)+(a^48),a=getchar(); } int dis[13][13],s[13],dep[13];//s是每次要打乱的顺序队列 int main() { int n,m,x,y,z,v,mv,mp,ans=0x3f3f3f3f;scanf("%d%d",&n,&m); memset(dis,0x3f,sizeof(dis)); for(int i=1;i<=n;++i)dis[i][i]=0,s[i]=i; while(m--) { read(x);read(y);read(z); if(dis[x][y]>z) dis[x][y]=z,dis[y][x]=z; } //为保证正确性，卡住时间，多随机几次 for(int times=1;times<=100000;++times) { random_shuffle(s+1,s+1+n);v=0; memset(dep,0,sizeof(dep)); dep[s[1]]=1;//第一个屋子 for(int i=2;i<=n;++i) { int t=s[i];mv=INF;mp=0; for(int j=1;j<=n;++j) { if(!dep[j]||dis[j][t]==INF)continue; //若前一个屋子未被开发，或路径不存在，就继续 if(mv>dis[j][t]*dep[j])mv=dis[j][t]*dep[j],mp=j; }if(!mp)goto end; //偷懒用了goto，若当前点无屋子可到，则放弃此次随机。 dep[t]=dep[mp]+1;v+=mv; } ans=min(ans,v);end:; //每次取ans最小 } printf("%d",ans); return 0; } ```