2018.08.09洛谷P3959 宝藏（随机化贪心）

传送门
回想起了自己赛场上乱搜的20分。
好吧现在也就是写了一个随机化贪心就水过去了，不得不说随机化贪心大法好。
代码：

#include<bits/stdc++.h> using namespace std; inline int read(){int ans=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans; } int up,cost[20][20],n,m,dep[20],p[20],ans,sum; int main(){n=read(),m=read(),up=1<<n;memset(cost,0x3f,sizeof(cost));ans=0x3f3f3f3f;for(int i=1;i<=n;++i)cost[i][i]=0,p[i]=i;for(int i=1;i<=m;++i){int u=read(),v=read(),w=read();cost[u][v]=cost[v][u]=min(cost[u][v],w);}for(int tim=1;tim<=80000;++tim){random_shuffle(p+1,p+n+1);sum=0;for(int i=1;i<=n;++i)dep[i]=0;dep[p[1]]=1;bool f=true;for(int i=2;i<=n;++i){int pos=p[i],stp=0x3f3f3f3f;for(int j=1;j<=n;++j)if(j!=pos&&dep[j]&&cost[pos][j]!=0x3f3f3f3f)if(dep[j]*cost[pos][j]<stp)stp=dep[j]*cost[pos][j],dep[pos]=dep[j]+1;if(stp==0x3f3f3f3f){f=false;break;}sum+=stp;}if(f)ans=min(ans,sum);}cout<<ans;return 0; }

转载于:https://www.cnblogs.com/ldxcaicai/p/9738390.html

总结

以上是生活随笔为你收集整理的2018.08.09洛谷P3959 宝藏（随机化贪心）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。