一 原问题链接

Jungle Roads - POJ 1251 - Virtual Judge

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

二 输入和输出

1 输入

输入由1~100个数据集组成，最后一行只包含0.每个数据集的第1行都为数字n，表示村庄的数量，对村庄使用字母表的前 n 个大写字母标记。每个数据集都有 n-1 行描述，这些行的村庄标签字母顺序排序。最后一个村庄没有道路。村庄的每条道路都以村庄标签开头，后面跟着一个从这个村庄到后面村庄的道路数k。如果k>0,则该行后面跟着一个从这个村庄到后面村庄的道路数k。如果 k>0,则该行后面包含 k 条道路数据。每条道路的数据都是道路另一端的标签，后面是道路的每月维护成本。

2 输出

对于每个数据集，都单行输出每月维护连接所有村庄的道路的最低费用。

三 输入和输出样例

1 输入样例

9

A 2 B 12 I 25

B 3 C 10 H 40 I 8

C 2 D 18 G 55

D 1 E 44

E 2 F 60 G 38

F 0

G 1 H 35

H 1 I 35

3

A 2 B 10 C 40

B 1 C 20

0

2 输出样例

216

30

四 分析

这是非常简单的最小生成树问题，只需计算最小生成树的和值即可。使用 Prim 或 Kruskal 算法均可求解。

五 代码

package graph.poj1251;

import java.util.Scanner;

public class Poj1251 {
    static int[] m[] = new int[30][30];
    static int dis[] = new int[30];
    static boolean vis[];
    static int n;

    static int prim(int s) {
        for (int i = 0; i < n; i++)
            dis[i] = m[s][i];
        vis = new boolean[30];
        vis[s] = true;
        int sum = 0;
        int t = 0;
        for (int i = 1; i < n; i++) {
            int min = 0x3f3f3f3f;
            for (int j = 0; j < n; j++) { // 找最小
                if (!vis[j] && dis[j] < min) {
                    min = dis[j];
                    t = j;
                }
            }
            sum += min;
            vis[t] = true;
            for (int j = 0; j < n; j++) { // 更新
                if (!vis[j] && dis[j] > m[t][j])
                    dis[j] = m[t][j];
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            n = scanner.nextInt();
            if (n == 0) {
                return;
            }

            int num, w;
            char c;

            for (int i = 0; i < m.length; i++) {
                for (int j = 0; j < m[0].length; j++) {
                    m[i][j] = 0x3f3f3f3f; // 分别赋值
                }
            }

            for (int i = 1; i < n; i++) {
                c = scanner.next().charAt(0);
                num = scanner.nextInt();
                int u = c - 'A';
                while (num-- > 0) {
                    c = scanner.next().charAt(0);
                    w = scanner.nextInt();
                    int v = c - 'A';
                    if (w < m[u][v])
                        m[u][v] = m[v][u] = w;
                }
            }
            System.out.println(prim(0));
        }
    }
}

六 测试

绿色为输出，白色为输出