最小生成树

Prim 算法

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

boolean[] vis = new boolean[N];
List<node>[] G = new List[N];

void init() 
{
    for(int i = 0; i < N; i++)
        G[i] = new ArrayList<>();
}

int prim()
{
    Queue<node> q = new PriorityQueue<>((a, b) -> {
        return a.dis - b.dis;
    });

    q.add(new node(1, 0));

    int cnt = 0, res = 0;
    while(q.size() > 0)
    {
        node t = q.poll();
        if(vis[t.v])   continue;
        cnt ++;
        res += t.dis;
        vis[t.v] = true;
        if(cnt == n)    return res;
        for(node v : G[t.v]) {
            if(!vis[v.v]) {
                q.add(new node(v.v, v.dis));
            }
        }
    }
    return inf;
}

Kruskal 算法

import java.io.*;
import java.util.*;
import java.lang.*;
import java.math.*;

public class Main {

    Scanner sin = new Scanner(System.in);
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer cin = new StreamTokenizer(in);
    PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));

    final int N = 100010, mod = (int)(1e9+7), inf = 0x3f3f3f3f;

    int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }

    String next() throws Exception {
        cin.nextToken();
        return cin.sval;
    }

    class Edge
    {
        int a,b,w;
        Edge(int w,int a,int b)
        {
            this.a=a;
            this.b=b;
            this.w=w;
        }
    };

    Edge[] G = new Edge[2 * N];
    int[] fa = new int[N];
    int n, m;

    void init() {
        for (int i = 1; i < N; i++)
            fa[i] = i;
    }

    int find(int x){
        if(fa[x] != x)  return fa[x] = find(fa[x]);
        return fa[x] = x;
    }

    boolean merge(int x, int y) {
        int a = find(x), b = find(y);
        if(a != b){
            fa[a] = b;
            return true;
        }
        return false;
    }

    void kruskal() {
        Arrays.sort(G,1,1 + m,(x,y)-> {
            return x.w - y.w;
        });
        int res = 0, cnt = 0;
        for(int i = 1; i <= m; i ++)
            if (merge(G[i].a, G[i].b)) {
                cnt ++; 
                res += G[i].w;
            }

        if(cnt < n-1)   cout.print("impossible");
        else cout.print(res);
    }

    void solve() throws Exception {
        init();
        n = nextInt();
        m = nextInt();
        for(int i = 1; i <= m; i ++)
        {
            int a = nextInt(), b = nextInt(), w = nextInt();
            G[i] = new Edge(w,a,b);
        }
        kruskal();
    }

    public static void main(String[] args) throws Exception {
        Main cmd = new Main();
        cmd.solve();
        cmd.cout.close();
    }
}