一 原问题链接

Networking - POJ 1287 - Virtual Judge

https://vjudge.net/problem/POJ-1287

二 输入和输出

1 输入

输入由多个数据集组成，每个数据集都描述一个网络。数据集的第1行包括两个整数：第1个整数表示点数P，节点标号为1~P；第2个整数表点之间的路线数R。以下 R 行为点之间的路线，每条路线包括3个整数：前两个整数为点标号，第3个整数为路线长度L。数据集之间以空格分隔，输入仅有一个数字P（p=0），表示输入结束。

2 输出

对于每个数据集，都单行输出所设计网络的电缆的最小总长度。

三 输入和输出样例

1 输入样例

1 0

2 3

1 2 37

2 1 17

1 2 68

3 7

1 2 19

2 3 11

3 1 7

1 3 5

2 3 89

3 1 91

1 2 32

5 7

1 2 5

2 3 7

2 4 8

4 5 11

3 5 10

1 5 6

4 2 12

0

2 输出样例

0

17

16

26

四 算法设计

本问题是简单的最小生成树问题，可以采用 Prim 或 Kruskal 算法求解。在此使用并查集优化的 Kruskal 算法。

1 初始化。将所有的边都按权值从小到大排序，将每个节点的集合号都初始化为自身编号。

2 按排序后的顺序选择权值最小的边(u,v)。

3 如果节点 u 和 v 属于两个不同的连通分支，则采用并查集对两个连通分支进行合并，累加边（u,v）的权值。

4 如果选择的边数小于 n-1，则转向步骤2，否则算法结束，返回和值。

五 代码

package graph.poj1287;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class POJ1287 {
    static int fa[] = new int[55];
    static int n;
    static int m;
    static int cnt;

    static node edge[] = new node[3000];
    static List<node> nodeList = new ArrayList();

    static void add(int a, int b, int c) {
        edge[cnt].u = a;
        edge[cnt].v = b;
        edge[cnt].cost = c;
        nodeList.add(edge[cnt]);
        cnt++;
    }

    static int find(int x) { // 并查集找祖宗
        if (x != fa[x]) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

    // 合并
    static boolean merge(int a, int b) {//集合合并
        int x = find(a);
        int y = find(b);
        if (x == y) return false;
        fa[y] = x;
        return true;
    }

    static int kruskal() {
        int sum = 0;
        Collections.sort(nodeList);
        for (int i = 0; i < m; i++) {
            if (merge(nodeList.get(i).u, nodeList.get(i).v)) {
                sum += nodeList.get(i).cost;
                if (--n == 1)
                    return sum;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int x, y, z;
        while (true) {
            n = scanner.nextInt();
            if (n == 0) return;
            nodeList.clear();
            for (int i = 0; i < edge.length; i++) {
                edge[i] = new node();
            }

            cnt = 0;
            m = scanner.nextInt();
            for (int i = 1; i <= n; i++)
                fa[i] = i;
            for (int i = 0; i < m; i++) {
                x = scanner.nextInt();
                y = scanner.nextInt();
                z = scanner.nextInt();
                add(x, y, z);
            }
            System.out.println(kruskal());
        }
    }
}

class node implements Comparable {
    int u;
    int cost;
    int v;

    @Override
    public int compareTo(Object o) {
        if (this.cost > ((node) o).cost) {
            return 1;
        } else if (this.cost == ((node) o).cost) {
            return 0;
        } else {
            return -1;
        }
    }
}

六 测试

绿色为输入，白色为输出