53.尋寶
題目：53. 尋寶（第七期模擬筆試） (kamacoder.com)
思路：首先，我不知道怎么存這樣的東西，用三維數組嗎，沒搞懂，果斷放棄
prim算法實現
import java.util.*;class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int v = scanner.nextInt();int e = scanner.nextInt();// 填一個默認最大值，題目描述val最大為10000int[][] grid = new int[v + 1][v + 1];for (int i = 1; i <= v; i++) {Arrays.fill(grid[i], 10001);}for (int i = 0; i < e; i++) {int x = scanner.nextInt();int y = scanner.nextInt();int k = scanner.nextInt();// 因為是雙向圖，所以兩個方向都要填上grid[x][y] = k;grid[y][x] = k;}// 所有節點到最小生成樹的最小距離int[] minDist = new int[v + 1];Arrays.fill(minDist, 10001);// 這個節點是否在樹里boolean[] isInTree = new boolean[v + 1];// 我們只需要循環 n-1次，建立 n - 1條邊，就可以把n個節點的圖連在一起for (int i = 1; i < v; i++) {// 1、prim三部曲，第一步：選距離生成樹最近節點int cur = -1; // 選中哪個節點 加入最小生成樹int minVal = Integer.MAX_VALUE;for (int j = 1; j <= v; j++) { // 1 - v，頂點編號，這里下標從1開始// 選取最小生成樹節點的條件：// （1）不在最小生成樹里// （2）距離最小生成樹最近的節點if (!isInTree[j] && minDist[j] < minVal) {minVal = minDist[j];cur = j;}}// 2、prim三部曲，第二步：最近節點（cur）加入生成樹isInTree[cur] = true;// 3、prim三部曲，第三步：更新非生成樹節點到生成樹的距離（即更新minDist數組）// cur節點加入之后， 最小生成樹加入了新的節點，那么所有節點到 最小生成樹的距離（即minDist數組）需要更新一下// 由于cur節點是新加入到最小生成樹，那么只需要關心與 cur 相連的 非生成樹節點 的距離 是否比 原來 非生成樹節點到生成樹節點的距離更小了呢for (int j = 1; j <= v; j++) {// 更新的條件：// （1）節點是 非生成樹里的節點// （2）與cur相連的某節點的權值 比 該某節點距離最小生成樹的距離小// 很多錄友看到自己 就想不明白什么意思，其實就是 cur 是新加入 最小生成樹的節點，那么 所有非生成樹的節點距離生成樹節點的最近距離 由于 cur的新加入，需要更新一下數據了if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}}}// 統計結果int result = 0;for (int i = 2; i <= v; i++) { // 不計第一個頂點，因為統計的是邊的權值，v個節點有 v-1條邊result += minDist[i];}System.out.println(result);}
}
小結
prim算法的關鍵是加點。
prim三步曲
- 第一步，選距離生成樹最近節點
- 第二步，最近節點加入生成樹
- 第三步，更新非生成樹節點到生成樹的距離（即更新minDist數組）
Kruskal 算法實現
import java.util.*;class Edge implements Comparable<Edge> {int l, r, val;Edge(int l, int r, int val) {this.l = l;this.r = r;this.val = val;}@Overridepublic int compareTo(Edge other) {return Integer.compare(this.val, other.val);}
}class Main {private static int[] father;// 并查集初始化public static void init(int n) {father = new int[n];for (int i = 0; i < n; ++i) {father[i] = i;}}// 并查集的查找操作public static int find(int u) {return u == father[u] ? u : (father[u] = find(father[u])); // 路徑壓縮}// 并查集的加入集合public static void join(int u, int v) {u = find(u); // 尋找u的根v = find(v); // 尋找v的根if (u != v) { // 如果發現根不同，則將v的根指向u的根father[v] = u;}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int v = scanner.nextInt();int e = scanner.nextInt();List<Edge> edges = new ArrayList<>();for (int i = 0; i < e; i++) {int v1 = scanner.nextInt();int v2 = scanner.nextInt();int val = scanner.nextInt();edges.add(new Edge(v1, v2, val));}// 按邊的權值對邊進行從小到大排序Collections.sort(edges);// 并查集初始化init(v + 1); // 初始化大小為 v + 1 的并查集，因為節點編號是從 1 開始int result_val = 0;// 從頭開始遍歷邊for (Edge edge : edges) {// 并查集，搜出兩個節點的祖先int x = find(edge.l);int y = find(edge.r);// 如果祖先不同，則不在同一個集合if (x != y) {result_val += edge.val; // 這條邊可以作為生成樹的邊join(x, y); // 兩個節點加入到同一個集合}}System.out.println(result_val);scanner.close();}
}
小結
- Kruskal算法需要自定義一個數據結構Edge，存放邊和權值
- 為了方便比較，需要實現Comparable接口
kruscal的思路：
- 邊的權值排序，因為要優先選最小的邊加入到生成樹里
- 遍歷排序后的邊
- 如果邊的兩個節點在同一個集合，說明如果連上這條邊圖中會出現環
- 如果邊的兩個節點不在同一個集合，加入到最小生成樹，并把兩個節點加入同一個集合
（下）)
)
)
