P3366 【模板】最小生成树 java prim算法 洛谷

        传送门:

P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P3366        这道题有两种常规做法，kruskal(对边进行研究) 和 prim(对节点进行研究，类似dijikstra）。本文主要讲解prim算法。

        Prim和最短路中的dijkstra很像，由于速度问题，所以这里我用链式前向星存图。Prim的思想是将任意节点作为根，再找出与之相邻的所有边（用一遍循环即可），再将新节点更新并以此节点作为根继续搜，维护一个数组：dis，作用为已用点到未用点的最短距离。

        证明：Prim算法之所以是正确的，主要基于一个判断：对于任意一个顶点v，连接到该顶点的所有边中的一条最短边(v, vj)必然属于最小生成树（即任意一个属于最小生成树的连通子图，从外部连接到该连通子图的所有边中的一条最短边必然属于最小生成树）  

        相比于kruskal算法的O(eloge)复杂度，prim时间复杂度为。可见，针对不同题目的不同的n和m的取值，我们可以依据实际情况选择kruskal和prim。

         学过dijistra的小伙伴应该一下就能理解下面的代码:

import java.io.*;
import java.util.*;

class node{
    int pos,dis;
    public node(int pos,int dis){
        this.pos = pos;
        this.dis = dis;
    }
}

public class Main {
    static int N=5001,M=200001;
    static int n,m,cnt,ans,idx;
    static int[] vv = new int[M<<1], to = new int[M<<1];
    static int[] ww = new int[M<<1], he = new int[N];
    static int[] dis = new int[N];
    static boolean[] vis = new boolean[N];
    public static void main(String[] args) throws IOException {
        n=nextInt();
        m=nextInt();
        for(int i=1;i<=m;i++) {
            int u=nextInt(),v=nextInt(),w=nextInt();
            addEdge(u,v,w);
            addEdge(v,u,w);
        }
        prim(1);
        if(idx == n) out.println(ans);
        else out.println("orz");
        out.close();
    }

    public static void prim(int root) {
        PriorityQueue<node> queue = new PriorityQueue<>((o1, o2) -> (o1.dis-o2.dis));
        Arrays.fill(dis, 0x3f3f3f3f);
        dis[root] = 0;
        queue.offer(new node(root,0));
        while(!queue.isEmpty() && idx<n) {
            node tmp = queue.remove();
            int u = tmp.pos;
            int w = tmp.dis;
            if(vis[u]) continue;
            vis[u] = true;
            ans+=w;
            idx++;
            for(int i=he[u];i>0;i=to[i]){
                int v=vv[i];
                if(ww[i] < dis[v]) {
                    dis[v] = ww[i];
                    queue.offer(new node(v, ww[i]));
                }
            }
        }
    }

    public static void addEdge(int u,int v,int w){
        vv[++cnt]=v;
        ww[cnt]=w;
        to[cnt]=he[u];
        he[u]=cnt;
    }

    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    public static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    public static String nextString() throws IOException {
        in.nextToken();
        return in.sval;
    }
}