今天学长对比了最小生成树最快速的求法不管是稠密图还是稀疏图, 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\n",ans);
- else printf("orz\n");
- return 0;
- }
来源: https://www.cnblogs.com/chdy/p/9675948.html