最小生成树

Prim 算法

假设所求图是连通的，求它的最小连通图。

1. 设集合S为已确定的局部最小连通图，初始时S={a}，a为任意一点；
2. 找出与S中连接着的权值最小的点t，将它加入集合S中；
   重复步骤 2 直至所有点均连通。

Prim 算法跟单源最短路径算法 Dijkstra 很像，唯一不同的是在更新dist时，单源最短路径的做法是
dist[v] = min(dist[v], dist[u] + cost[u][v])
而 Prim 的做法是
dist[v] = min(dist[v], cost[u][v])

hdu1233
AC code

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

/**
 * @author hero
 */
public class Main implements Runnable {

    public void solve() {
        int MAX_COST = 1 << 24;
        int N;
        while ((N = nextInt()) != 0) {
            int[][] cost = new int[N + 1][N + 1];
            int[] dist = new int[N + 1];
            boolean[] visited = new boolean[N + 1];
            for (int i = 1; i <= N; i++) {
                dist[i] = MAX_COST;
                visited[i] = false;
                for (int j = 1; j <= i; j++) {
                    cost[i][j] = cost[j][i] = MAX_COST;
                }
            }
            int M = (N * (N - 1)) >> 1;
            for (int i = 0; i < M; i++) {
                int from = nextInt(), to = nextInt(), c = nextInt();
                cost[from][to] = cost[to][from] = c;
            }
            PriorityQueue<Edge> que = new PriorityQueue<>();
            dist[1] = 0;
            que.add(new Edge(0, 1));
            int result = 0;
            while (!que.isEmpty()) {
                Edge e = que.poll();
                if (!visited[e.to]) {
                    visited[e.to] = true;
                    result += e.cost;
                    for (int i = 1; i <= N; i++) {
                        if (!visited[i] && cost[e.to][i] != MAX_COST) {
                            if (cost[e.to][i] < dist[i]) {
                                dist[i] = cost[e.to][i];
                                que.add(new Edge(dist[i], i));
                            }
                        }
                    }
                }
            }
            out.println(result);
        }
    }

    static class Edge implements Comparable<Edge> {
        int cost;
        int to;

        public Edge(int cost, int to) {
            this.cost = cost;
            this.to = to;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }
    }

    public static void main(String[] args) {
        new Main().run();
    }

    @Override
    public void run() {
        init();
        solve();
        out.flush();
    }

    StreamTokenizer in;
    PrintWriter out;

    public void init() {
        in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(new OutputStreamWriter(System.out));
    }


    public int nextInt() {
        try {
            in.nextToken();
            return (int) in.nval;
        } catch (IOException e) {
            throw new Error(e);
        }
    }
}

Kruskal 算法

将 Edge<cost, from, to> 以 cost 按从小到大排序，设集合S={}为连通子集，直到所有点均连通为止。

边少的时候 Kruskal 效果好，点少的时候 Prim 效果好，此题 Prim 用时更少。

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

/**
 * @author hero
 */
public class Main implements Runnable {

    public void solve() {
        int N;
        while ((N = nextInt()) != 0) {
            int[] par = new int[N + 1];
            for (int i = 1; i <= N; i++) {
                par[i] = i;
            }
            PriorityQueue<Edge> que = new PriorityQueue<>();
            int M = (N * (N - 1)) >> 1;
            for (int i = 0; i < M; i++) {
                int from = nextInt(), to = nextInt(), c = nextInt();
                que.add(new Edge(c, from, to));
            }
            int result = 0;
            while (!que.isEmpty()) {
                Edge e = que.poll();
                if (lookup(par, e.from) != lookup(par, e.to)) {
                    result += e.cost;
                    collect(par, e.from, e.to);
                }
            }
            out.println(result);
        }
    }

    public void collect(int[] par, int u, int v) {
        int pu = lookup(par, u), pv = lookup(par, v);
        if (pu < pv) {
            par[pv] = pu;
        } else par[pu] = pv;
    }

    public int lookup(int[] par, int u) {
        int t = u, v;
        while (par[t] != t) t = par[t];
        while (par[u] != t) {
            v = par[u];
            par[u] = t;
            u = v;
        }
        return t;
    }

    static class Edge implements Comparable<Edge> {
        int cost;
        int from;
        int to;

        public Edge(int cost, int from, int to) {
            this.cost = cost;
            this.from = from;
            this.to = to;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }
    }

    public static void main(String[] args) {
        new Main().run();
    }

    @Override
    public void run() {
        init();
        solve();
        out.flush();
    }

    StreamTokenizer in;
    PrintWriter out;

    public void init() {
        in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(new OutputStreamWriter(System.out));
    }


    public int nextInt() {
        try {
            in.nextToken();
            return (int) in.nval;
        } catch (IOException e) {
            throw new Error(e);
        }
    }
}