今天学长对比了最小生成树最快速的求法不管是稠密图还是稀疏图，prim+邻接表+堆优化都能得到一个很不错的速度，所以参考学长的代码打出了下列代码，make_pair还不是很会，大体理解的意思是可以同时绑定两种元素（和struct差不多）但加入堆的时候以第一个元素来进行优先队列，建立的是大根堆由于每次要选出最小的边所以把边取反，最小的那个边加上符号就变成最大的了，大体上就是这样。prim的思想。
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<vector> #include<queue> #include<stack> #include<map> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } priority_queue<pair<int,int> >q; int nex[200001<<1],ver[200001<<1],e[200001<<1],lin[200001<<1],len=0; void add(int x,int y,int z) { ver[++len]=y; nex[len]=lin[x]; lin[x]=len; e[len]=z; } int n,m; int vis[5009],d[5009]; int ans=0,cnt=0; void prim() { memset(vis,0,sizeof(vis)); memset(d,10,sizeof(d)); d[1]=0;q.push(make_pair(0,1)); while(q.size()!=0&&cnt<n)//注意这个地方是和，两个之中有一个不满足就退出 { int u=q.top().second,dis=-q.top().first;q.pop(); if(vis[u]==1)continue; ans+=dis;vis[u]=1;cnt++; for(int i=lin[u];i;i=nex[i]) { int tn=ver[i]; if(e[i]<d[tn]) { d[tn]=e[i];q.push(make_pair(-d[tn],tn)); } } } } int main() { freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=m;i++) { int x,y,z; x=read();y=read();z=read(); add(x,y,z); add(y,x,z); } prim(); if(cnt==n) printf("%d ",ans); else printf("orz "); return 0; }
多情自古原多病，清镜怜清影。