53.寻宝（第七期模拟笔试）
题目描述
在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。
给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。
输入描述
第一行包含两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。
接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。
输出描述
输出联通所有岛屿的最小路径总距离
输入示例
7 11
1 2 1
1 3 1
1 5 2
2 6 1
2 4 2
2 3 2
3 4 1
4 5 1
5 6 2
5 7 1
6 7 1
输出示例
6
提示信息
数据范围：
2 <= V <= 10000;
1 <= E <= 100000;
0 <= val <= 10000;如下图，可见将所有的顶点都访问一遍，总距离最低是6.
解题思路
prime解法
核心思想是以节点为准，查找相关的权值最小的边。自己起初用邻接矩阵写的，遍历要遍历N^2。
import java.util.*;
class Main {
public static int prime(int[][] graph, boolean[] visited) {
int min = Integer.MAX_VALUE;
int choose = -1;
for (int i = 0; i < graph.length; i++) {
if (!visited[i]) {
continue;
}
for (int j = 0; j < graph.length; j++) {
if (!visited[j] && graph[i][j] > 0) {
if (min > graph[i][j]) {
min = graph[i][j];
choose = j;
}
}
}
}
if (choose == -1) {
return 0;
}
visited[choose] = true;
return prime(graph, visited) + min;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int v = in.nextInt(), e = in.nextInt();
int[][] graph = new int[v][v];
for (int i = 0; i < e; i++) {
int v1 = in.nextInt() - 1;
int v2 = in.nextInt() - 1;
int val = in.nextInt();
graph[v1][v2] = val;
graph[v2][v1] = val;
}
in.close();
boolean[] visited = new boolean[v];
visited[0] = true;
int ans = prime(graph, visited);
System.out.println(ans);
}
}
邻接表优化思路
使用邻接表+优先队列的方式，将起始点有关的边加入进去。然后维护这个优先队列，每次取堆顶就行了。直到所有顶点都已经被访问。
import java.util.*;
class Main {
static class Edge {
int to, val;
Edge(int to, int val) {
this.to = to;
this.val = val;
}
}
public static int prime(List<Edge>[] graph, int n) {
boolean[] visited = new boolean[n];
PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.val));
visited[0] = true;
for (Edge e : graph[0]) {
pq.offer(e);
}
int ans = 0, cnt = 1;
while (!pq.isEmpty() && cnt < n) {
Edge cur = pq.poll();
if (visited[cur.to]) {
continue;
}
visited[cur.to] = true;
ans += cur.val;
cnt++;
for (Edge next : graph[cur.to]) {
if (!visited[next.to]) {
pq.offer(next);
}
}
}
// 图不连通则不存在最小生成树
if (cnt < n) {
throw new RuntimeException("图不连通，最小生成树不存在");
}
return ans;
}
static List<Edge>[] constructGraph() {
Scanner in = new Scanner(System.in);
int v = in.nextInt(), e = in.nextInt();
List<Edge>[] graph = new ArrayList[v];
for (int i = 0; i < v; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < e; i++) {
int v1 = in.nextInt() - 1;
int v2 = in.nextInt() - 1;
int val = in.nextInt();
graph[v1].add(new Edge(v2, val));
graph[v2].add(new Edge(v1, val));
}
in.close();
return graph;
}
public static void main(String[] args) {
List<Edge>[] graph = constructGraph();
int v = graph.length;
int ans = prime(graph, v);
System.out.println(ans);
}
}
Kruskal解法
import java.util.*;
class Main {
static class Edge {
int v, u, val;
Edge(int v, int u, int val) {
this.v = v;
this.u = u;
this.val = val;
}
}
static class DSU {
int[] father;
DSU(int n) {
father = new int[n];
for (int i = 0; i < n; i++) {
father[i] = i;
}
}
int find(int x) {
return father[x] == x ? x : (father[x] = find(father[x]));
}
boolean union(int a, int b) {
int ra = find(a);
int rb = find(b);
if (ra == rb) {
return false;
}
father[ra] = rb;
return true;
}
}
public static int kruskal(List<Edge> edges, int n) {
Collections.sort(edges, Comparator.comparingInt(e -> e.val));
DSU dsu = new DSU(n);
int ans = 0, cnt = 0;
for (Edge edge : edges) {
if (dsu.union(edge.v, edge.u)) {
ans += edge.val;
cnt++;
if (cnt == n - 1) break;
}
}
return ans;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int v = in.nextInt(), e = in.nextInt();
List<Edge> edges = new ArrayList<>();
for (int i = 0; i < e; i++) {
int v1 = in.nextInt() - 1;
int v2 = in.nextInt() - 1;
int val = in.nextInt();
edges.add(new Edge(v1, v2, val));
edges.add(new Edge(v2, v1, val));
}
in.close();
int ans = kruskal(edges, v);
System.out.println(ans);
}
}
评论