当前位置：首页 > news >正文

代码随想录算法训练营第四十九天

news 2025/5/25 13:20:58

卡码网题目:

53. 寻宝（第七期模拟笔试）

其他:

今日总结
往期打卡

53. 寻宝（第七期模拟笔试）

跳转: 53. 寻宝（第七期模拟笔试）

学习: 代码随想录公开讲解

问题:

在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。

不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将所有岛屿联通起来（注意：这是一个无向图）。

给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。

思路:

Prime算法,找一个起点一层层更新最小值,和Dijkstra类似,更新后是距离树的值,不用加起点到当前.
一共三步操作
扫描一遍找到当前树可到达的最近节点
记录最近节点(加入生成树)
用最近节点更新到达各节点的最近距离.

复杂度:

时间复杂度: $O(n^2)$
空间复杂度: $O(n^2)$

代码(朴素Prime):

import java.util.*;
class Main{private static int[] dist;private static int n;private static int[][] w;private static final int INF = 0x3f3f3f3f;public static void main(String[] args){Scanner scanner = new Scanner(System.in);n = scanner.nextInt();int m = scanner.nextInt();dist = new int[n+1];w = new int[n+1][n+1];// for(int i = 0;i <= n;i++){//     for(int j = 0;j <= n;j++){//         w[i][j] = i == j ? 0 : INF;//     }// }for(int i = 0;i <= n;i){Arrays.fill(w[i],INF);}for(int i = 0;i < m;i++){int u = scanner.nextInt(),v = scanner.nextInt(),weight = scanner.nextInt();w[u][v] = w[v][u] = weight;}prime();int ans = 0;for(int i = 2;i <= n;i++){ans += dist[i];}System.out.println(ans);scanner.close();}private static void prime(){Arrays.fill(dist,INF);boolean[] vis = new boolean[n + 1];dist[1] = 0;for(int i = 1;i <= n;i++){int minIdx = -1;for(int j = 1;j <= n;j++){if(vis[j]) continue;if(minIdx==-1||dist[minIdx]>dist[j]){minIdx = j;}}vis[minIdx] = true;for(int j = 1;j <= n;j++){if(vis[j]) continue;if(dist[j]>w[minIdx][j]){dist[j] = w[minIdx][j];}}}}}

复杂度:

时间复杂度: $O(n^2)$
空间复杂度: $O (n l o g m)$

代码(优先队列+链式前向星Prime):

import java.util.*;
class Main{private static int[] dist;private static int n;private static int idx;private static int[] head,e,next,w;private static final int INF = 0x3f3f3f3f;private static void add(int u, int v, int weight){e[idx] = v;next[idx] = head[u];w[idx] = weight;head[u] = idx++;}public static void main(String[] args){Scanner scanner = new Scanner(System.in);n = scanner.nextInt();int m = scanner.nextInt();dist = new int[n+1];head = new int[n+1];Arrays.fill(head,-1);e = new int[m*2];next = new int[m*2];w = new int[m*2];for(int i = 0;i < m;i++){int u = scanner.nextInt(),v = scanner.nextInt(),weight = scanner.nextInt();add(u,v,weight);add(v,u,weight);}prime();int ans = 0;for(int i = 1;i <= n;i++){ans += dist[i];}System.out.println(ans);}private static void prime(){Arrays.fill(dist,INF);boolean[] vis = new boolean[n + 1];dist[1] = 0;PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(x->x[1]));queue.offer(new int[]{1,0});while(!queue.isEmpty()){int poll = queue.poll()[0];if(vis[poll]) continue;vis[poll] = true;for(int i = head[poll];i != -1;i = next[i]){int j = e[i];if(vis[j]||w[i]>=dist[j]) continue;dist[j] = w[i];queue.add(new int[]{j,dist[j]});}}}}

思路:

Kruskal,从权最小的边开始连接,只要不构成环就合法.
使用并查集检测环.

复杂度:

时间复杂度: $O(n^2)$
空间复杂度: $O (m l o g m)$

代码(Kruskal):

import java.util.*;class Main{static class DisJoint{int[] parent;DisJoint(int n){parent = new int[n + 1];for(int i = 1;i <= n;i++){parent[i] = i;}}public int find(int x){return x==parent[x]?x:(parent[x]=find(parent[x]));}public boolean isSame(int a,int b){return find(a) == find(b);}public void join(int _a,int _b){int a = find(_a);int b = find(_b);if(a==b) return;parent[b] = a;}}static class Edge{int s;int e;int w;Edge(int _s,int _e,int _w){s = _s;e = _e;w = _w;}}private static int n;private static final List<Edge> edges = new ArrayList<>();public static void main(String[] args){Scanner scanner = new Scanner(System.in);n = scanner.nextInt();int m = scanner.nextInt();for(int i = 0;i < m;i++){int u = scanner.nextInt(),v = scanner.nextInt(),w = scanner.nextInt();edges.add(new Edge(u,v,w));}System.out.println(Kruskal());scanner.close();}private static int Kruskal() {int ans = 0;DisJoint disJoint = new DisJoint(n);edges.sort(Comparator.comparing(x->x.w));for(Edge i:edges){if(disJoint.isSame(i.s,i.e)) continue;disJoint.join(i.s,i.e);ans += i.w;}return ans;}}