prim吗？写链式前向星的话
by liubw_ @ 2021-11-15 23:18:37
每次贪心的找个最近的点更新，类似于dij，但更新方法不完全一样，我上网找个板子就好了
~~题解里就有吧~~
by liubw_ @ 2021-11-15 23:21:02
ssd,jbl
by raincity @ 2021-11-15 23:24:57
```cpp
// Problem: P3366 【模板】最小生成树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3366
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N=5050,M=2e5+50;
const int INF=1e9+10;
inline int read(){
int ret=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-') f=-f; ch=getchar(); }
while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline void write(int x){
if(x<0){ putchar('-'); x=-x; }
if(x>9) write(x/10);
putchar(x%10+'0');
}
struct Edge{
int to;
int w;
int nx;
}e[M<<1];
int hd[N];
int tot;
void Add(int u,int v,int w){
e[++tot]={v,w,hd[u]};
hd[u]=tot;
}
int dis[N];
struct Node{
int id;
int val;
bool operator<(const Node &B)const{
return val>B.val;
}
};
void Prim(int n,int m,int s){
int MST=0;
priority_queue<Node> hp;
bitset<N> vis;
fill(dis+1,dis+n+1,INF);
dis[s]=0;
hp.push({s,dis[s]});
while(!hp.empty()){
int u=hp.top().id; hp.pop();
if(vis[u]) continue;
vis[u]=1;
MST+=dis[u];
for(int i=hd[u];i;i=e[i].nx){
int v=e[i].to,w=e[i].w;
if(vis[v]) continue;
if(w<dis[v]){
dis[v]=w;
hp.push({v,dis[v]});
}
}
}
int flag=1;
for(int i=1;i<=n;++i) flag&=vis[i];
if(flag) write(MST);
else puts("orz");
}
int n,m;
int main(){
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(n,m,1);
return 0;
}
```
不需要判重边，因为一定会被更优的边覆盖，另外大根堆重载要反着写$qwq$
by Christophe_ @ 2022-07-30 10:24:33