题解 P3366 【【模板】最小生成树】
yhtwd
2017-11-09 11:32:05
#Prim+邻接链表
看了一下其他人的，发现好像都没有我的堆优化过后的Prim要快，堆优化之后的Prim总共只要180ms，而且我要介绍一下我的毒瘤的Prim写法，看了一下网上的各种堆优化版本的Prim，都是直接存的边，代码冗长而难以理解，而既然Prim和Dijkstra的贪心思想是一样的并且也可以用类似的方法实现，那既然这样就可以用邻接链表存边并且像写Dijkstra一样写代码呀！我们可以分析一下直接存边和用邻接链表各自的优势：直接存边消耗的空间小因为存每条边的数据少而且不用因为是无向图而存两遍，但是直接存边由于不知道与该边相连的边是哪些，就需要O(N)的枚举或者用比邻接链表更多的空间来与预存下与每个点相连的边有那些。说真的，要用存边的方法写一个堆优化的Prim的代码真的其丑无比，所以这里我还是给大家推荐我的时间复杂度稳定在O(NlogN)的邻接链表版本堆优化Prim(讲了这么多结果还是在说代码的美观性……）
清爽的代码（不觉得清爽的可以看这些代码 [百度搜索:prim堆优化](https://www.baidu.com/s?ie=utf-8&f=3&rsv\_bp=1&rsv\_idx=1&tn=baidu&wd=prim%E5%A0%86%E4%BC%98%E5%8C%96&oq=prim%25E5%25A0%2586%25E4%25BC%2598%25E5%258C%2596%25E6%2597%25B6%25E9%2597%25B4%25E5%25A4%258D%25E6%259D%2582%25E5%25BA%25A6&rsv\_pq=8b20b8e70000c10f&rsv\_t=9c56PDP2aFCdoEf4Rga7fg0NNIRggz%2Fb3lNC1OWap5M0INl4O%2BuJ4BCfkko&rqlang=cn&rsv\_enter=0&inputT=1502&rsv\_sug3=54&rsv\_sug1=28&rsv\_sug7=000&prefixsug=prim%25E5%25A0%2586%25E4%25BC%2598%25E5%258C%2596&rsp=0&rsv\_sug4=2244&rsv\_sug=1)）：
```cpp
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define R register int
using namespace std;
int k,n,m,cnt,sum,ai,bi,ci,head[5005],dis[5005],vis[5005];
struct Edge
{
int v,w,next;
}e[400005];
void add(int u,int v,int w)
{
e[++k].v=v;
e[k].w=w;
e[k].next=head[u];
head[u]=k;
}
typedef pair <int,int> pii;
priority_queue <pii,vector<pii>,greater<pii> > q;
void prim()
{
dis[1]=0;
q.push(make_pair(0,1));
while(!q.empty()&&cnt<n)
{
int d=q.top().first,u=q.top().second;
q.pop();
if(vis[u]) continue;
cnt++;
sum+=d;
vis[u]=1;
for(R i=head[u];i!=-1;i=e[i].next)
if(e[i].w<dis[e[i].v])
dis[e[i].v]=e[i].w,q.push(make_pair(dis[e[i].v],e[i].v));
}
}
int main()
{
memset(dis,127,sizeof(dis));
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(R i=1;i<=m;i++)
{
scanf("%d%d%d",&ai,&bi,&ci);
add(ai,bi,ci);
add(bi,ai,ci);
}
prim();
if (cnt==n)printf("%d",sum);
else printf("orz");
}
```