Pime算法，16分求助

rb_tree @ 2024-08-08 14:23:40

#include<cstring>
#include<iostream>
#include<utility>
#include<queue>
using namespace std;
int n,m,h[5005],to[400005],nxt[400005],val[400005],ccnt,dis[5005],res=0,cnt=0;
bool vis[5005];
priority_queue<pair<int,int>,vector<pair<int,int> > ,greater<pair<int,int> > > q;
inline int read()
{
    int x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*w;
}
inline void write(long long x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>=10) write(x/10);
    putchar((x%10)+48);
    return;
}
inline void add_edge(int a,int b,int c)
{
    to[++cnt]=b;
    val[cnt]=c;
    nxt[cnt]=h[a];
    h[a]=cnt;
    return;
}
inline void Prim()
{
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    q.push(make_pair(1,0));
    while(!q.empty())
    {
        if(cnt>=n) break;
        int u=q.top().first,d=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        ++cnt;
        res+=d;
        for(int i=h[u];i;i=nxt[i])
        {
            int v=to[i],w=val[i];
            if(w<dis[v])
            {
                dis[v]=w;
                q.push(make_pair(dis[v],w));
            }
        }
    }
}
int main()
{
    n=read();
    m=read();
    for (int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    Prim();
    if(cnt==n) write(res);
    else printf("orz");
    return 0;
}

by ymx2009 @ 2024-08-08 14:36:13

pime是什么，人家叫Prim

by EityDawn @ 2024-08-08 14:39:09

@dou_wen_yuan 改好了，有两处错误

1. 入堆的应该是 {dis[v],v}
2. 记录达到的点数的cnt 与领接表的cnt 重复了

#include<cstring>
#include<iostream>
#include<utility>
#include<queue>
using namespace std;
int n,m,h[5005],to[400005],nxt[400005],val[400005],ccnt,dis[5005],res=0,cnt=0;
bool vis[5005];
priority_queue<pair<int,int>,vector<pair<int,int> > ,greater<pair<int,int> > > q;
inline int read()
{
    int x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*w;
}
inline void write(long long x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>=10) write(x/10);
    putchar((x%10)+48);
    return;
}
inline void add_edge(int a,int b,int c)
{
    to[++cnt]=b;
    val[cnt]=c;
    nxt[cnt]=h[a];
    h[a]=cnt;
    return;
}
int c=0;
inline void Prim()
{
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        if(c>=n) break;
        int u=q.top().second,d=q.top().first;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        ++c;
        res+=d;
        for(int i=h[u];i;i=nxt[i])
        {
            int v=to[i],w=val[i];
            if(w<dis[v])
            {
                dis[v]=w;
                q.push(make_pair(dis[v],v));
            }
        }
    }
}
int main()
{
    n=read();
    m=read();
    for (int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    Prim();
    if(c==n) write(res);
    else printf("orz");
    return 0;
}

by rb_tree @ 2024-08-08 14:43:36

@hgzx__lc 谢谢