求此题的链式前向星写法

P3366 【模板】最小生成树

lighthouse @ 2021-11-15 23:16:04

rt


by liubw_ @ 2021-11-15 23:18:37

prim吗?写链式前向星的话


by liubw_ @ 2021-11-15 23:21:02

每次贪心的找个最近的点更新,类似于dij,但更新方法不完全一样,我上网找个板子就好了

题解里就有吧


by raincity @ 2021-11-15 23:24:57

ssd,jbl


by Christophe_ @ 2022-07-30 10:24:33

// 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


|