https://www.luogu.org/blog/SkeletonSerpent/solution-p3959
by EternalAlexander @ 2018-02-20 14:53:29
@[EternalAlexander](/space/show?uid=48355) WA，清北学堂遇到的初中大佬
by Rye_Catcher @ 2018-02-20 15:44:22
@[EternalAlexander](/space/show?uid=48355) 原来是认识的
by 星星之火 @ 2018-02-20 15:51:22
@[EternalAlexander](/space/show?uid=48355) 大佬你发的代码有点问题
for (int i = 1; i < n; ++i) {
e=heap.top(); heap.pop();
while (!heap.empty()&&((vis[e.v]||rand()%(n)<1))) {//注意这里的判断条件rand()%n<1,即对于一个当前最近点，不选择的几率随着n的增大而减小。
if (!vis[e.v]) past[p++]=e;
//对于跳过了的边，以后还用得上，等待选择结束后再压回优先队列中
e=heap.top(); heap.pop();
} vis[e.v]=1; depth[e.v]=depth[e.u]+1;
if (p-->0) { //压回优先队列
for (;p>=0;--p) {
heap.push(past[p]);
}
}p=0;
for (int i = 1; i <= n; ++i) {
if (map[e.v][i]<inf&&!vis[i]) {
e2.u=e.v; e2.v=i;
heap.push(e2);
}
} cost+=map[e.u][e.v]*depth[e.u];
} return cost;
}
你在i里面又用了i
by 星星之火 @ 2018-02-20 21:29:46
@[星星之火](/space/show?uid=63019) 哪儿？
by EternalAlexander @ 2018-02-20 23:24:00
好吧，居然没有爆掉，奇迹
by EternalAlexander @ 2018-02-20 23:25:49
@[EternalAlexander](/space/show?uid=48355) 不知道为什么
by 星星之火 @ 2018-02-21 08:17:19
不会爆掉啊，会自动使用当前一层循环变量的啊@[星星之火](/space/show?uid=63019) @[EternalAlexander](/space/show?uid=48355)
by Captain_Paul @ 2018-03-26 16:06:54
http://touhou.studio/2018/03/27/NOIp2017-TG-Day2-T2-%E5%AE%9D%E8%97%8F/
by TimelyRain @ 2018-04-14 17:05:16
借用楼上大佬的SA的思想，同写了一份。
```cpp
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=13,inf=0x3f3f3f3f;
int map1[maxn][maxn],n,m,ans=0x3f3f3f3f;
bool vis[maxn];
struct node
{
int dep,w,id;
node(int x=0,int y=0,int z=0){dep=x,w=y,id=z;}
};
bool operator<(const node &a,const node &b)
{
return a.w>b.w;
}
void init()
{
ans=inf;
cin>>n>>m;
memset(map1,0x3f,sizeof(map1));
for(int i=1;i<=m;i++)
{
int x=0,y=0,z=0;
cin>>x>>y>>z;
map1[x][y]=min(map1[x][y],z);
map1[y][x]=min(map1[y][x],z);
}
}
void SA_prim()
{
for(int source=1;source<=n;source++)
{
node stack[10000];
int cost=0,top=0;
memset(vis,0,sizeof(vis));
vis[source]=true;
priority_queue<node>pq;
for(int i=1;i<=n;i++)
if(!vis[i]&&map1[source][i]!=inf)pq.push(node(2,map1[source][i],i));
for(int i=1;i<n;i++)
{
node temp=pq.top();
pq.pop();
while(!pq.empty()&&(vis[temp.id]||rand()%n==0))
{
if(!vis[temp.id])stack[++top]=temp;
temp=pq.top();
pq.pop();
}
while(top)pq.push(stack[top--]);
vis[temp.id]=true;
cost+=temp.w;
for(int j=1;j<=n;j++)
if(!vis[j]&&map1[temp.id][j]!=inf)pq.push(node(temp.dep+1,temp.dep*map1[temp.id][j],j));
}
ans=min(ans,cost);
}
}
int main()
{
srand(23177830);
init();
for(int i=1;i<=1000;i++)SA_prim();
cout<<ans;
return 0;
}
```
by ysj1173886760 @ 2018-08-21 08:32:09