一 原问题链接

Constructing Roads - POJ 2421 - Virtual Judge

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

二 输入和输出

1 输入

第 1 行是整数 N，表示村庄的数量；然后是 N 行，其中第 i 行包含 N 个整数，第 j 个整数表示村庄 i 和村庄 j 之间的距离；接着是整数 Q，表示已建成的道路的数量；然后是 Q 行，每行都包含两个整数 a 和 b，表示村庄 a 和村庄 b 之间的道路已经建成。

2 输出

单行输出需要构建的所有道路的最小长度。

三 输入和输出样例

1 输入样例

3

0 990 692

990 0 179

692 179 0

1

1 2

2 输出样例

179

四 分析

本问题属于最小生成树问题，不同的是本问题有一些道路已经建成，将这些道路的边权设置为0，然后采用 Prim 或 Kruskal 算法求解最小生成树即可。

五 代码

package graph.poj2421;

import java.util.Scanner;

public class POJ2421 {
    static final int maxn = 105;
    static final int inf = 0x3f3f3f3f;
    static int m[][] = new int[maxn][maxn];
    static int low[] = new int[maxn];
    static boolean vis[] = new boolean[maxn];
    static int n;

    static int prim(int s) {
        for (int i = 0; i < vis.length; i++) {
            vis[i] = false;
        }
        for (int i = 1; i <= n; i++)
            low[i] = m[s][i];
        vis[s] = true;
        int sum = 0;
        int t = 1;
        for (int i = 1; i < n; i++) { // 执行 n-1 次
            int min = inf;
            for (int j = 1; j <= n; j++) { // 找最小
                if (!vis[j] && low[j] < min) {
                    min = low[j];
                    t = j;
                }
            }
            sum += min;
            vis[t] = true;
            for (int j = 1; j <= n; j++) {//更新
                if (!vis[j] && low[j] > m[t][j])
                    low[j] = m[t][j];
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int q, a, b;
        while (true) {
            n = scanner.nextInt();
            if (n == 0) {
                return;
            }
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    m[i][j] = scanner.nextInt();
            q = scanner.nextInt();
            while (q-- > 0) {
                a = scanner.nextInt();
                b = scanner.nextInt();
                m[a][b] = m[b][a] = 0;
            }
            System.out.println(prim(1));
        }
    }
}

六 测试

绿色为输入，白色为输出。