prim—最小生成树

模板—最小生成树

int n,m,s;
int ne[N],h[N],idx,e[N],wt[N];//wt[]表示边权

void add(int u,int v,int w) //链式前向星存图
{
    idx++;
    e[idx]=v;
    wt[idx]=w; //边权
    ne[idx]=h[u];
    h[u]=idx;
}

int vis[N]; //vis[i]表示i点是否在s集合中
int d[N]; //d[i]表示 s->i 的最短路径

int p[N]; //p[i]表示i点是从哪个点过来的

int prim(int s)// 时间复杂度O(n^2);
{
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        d[i]=INF;
        //如果多次求d
        //要更新vis[]
        //要更新p[]
    }
    d[s]=0;
    //执行n次把点从t集合到s集合
    for(int i=1;i<=n;i++)
    {
        //1,找到最短路u
        int u=0;
        int minn=INF;
        for(int j=1;j<=n;j++)
        {
            //s集合与t集合的最短边
            if(d[j]<minn&&vis[j]==0)
            {
                u=j;
                //把最小值的下标给u
                minn=d[j];
                //把最小值给minn
            }
        }

        //2,把u移到s集合中
        vis[u]=1; //移到s集合中
        if(u==0)
        {
            return -1;
        }
        ans+=d[u];
        //3,在t集合中,跟u相邻的点进行松弛操作
        for(int j=h[u];j;j=ne[j])
        {
            int v=e[j];
            int w=wt[j];
            if(vis[v]==0&&d[v]>w)
            {
                d[v]=w;
            }
        }
    }
    return ans;
}
signed main()
{   fst;
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        u=read();
        v=read();
        w=read();
        add(u,v,w); //存图
        add(v,u,w);
    }
    int q=prim(1);
    if(q==-1)
    {
        cout<<"orz"<<endl;
    }
    else
    {
        cout<<q<<endl;
    }
    return 0;
}

int n, m, s;//堆优化
bool vis[N];
int d[N];

// 点u,d[u]

struct vnode
{
    int p;                               // 点
    int d;                               // 距离
    bool operator<(const vnode &b) const // 小顶堆——重载运算符
    {
        return d > b.d;
    }
};
vector<vnode> g[N];

int ans = 0;

int prim(int s)
{
    priority_queue<vnode> q;
    for (int i = 1; i <= n; i++)
    {
        d[i] = INF;
    }
    d[s] = 0;
    q.push({s, 0});
    while (!q.empty())
    {
        int u = q.top().p; // 找顶堆元素
        q.pop();
        if (vis[u]) // 如果已经找到了，就不用再操作了
        {
            continue;
        }
        // 如果在s集合中，就不用操作了，只有在t集合中，我们才拿进去，然后松弛
        vis[u] = 1;
        ans += d[u];
        for (auto e : g[u])
        {
            int v = e.p;
            int w = e.d;
            if (vis[v] == 0 && d[v] > w)
            {
                d[v] = w;
                q.push({v, d[v]});
            }
        }
    }
}
signed main()
{
    fst;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    prim(1);
    for (int i = 1; i <= n; i++)
    {
        if (d[i] == INF)
        {
            cout << "orz" << endl;
            return 0;
        }
    }
    cout << ans << endl;
    return 0;
}

JZTXT

prim算法

prim—最小生成树

模板—最小生成树

与Dijkstra算法类似，就在最后松弛操作时不同