解法一：Kruskal算法

思路

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.Arrays;
  5. import java.util.Comparator;
  7. public class Main {
  8.     public static void main(String[] args) throws IOException {
  9.         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  10.         String[] strs = reader.readLine().split(" ");
  11.         final int n = Integer.parseInt(strs[0]);
  12.         final int m = Integer.parseInt(strs[1]);
  13.         Point[] points = new Point[n + 1];
  14.         for (int i = 1; i <= n; ++i) {
  15.             points[i] = new Point(i);
  16.         }
  17.         Line[] lines = new Line[m];
  18.         Comparator<Line> lineComparator = new Comparator<Line>() {
  19.             @Override
  20.             public int compare(Line o1, Line o2) {
  21.                 return Integer.compare(o1.val, o2.val);
  23.             }
  24.         };
  25.         for (int i = 0; i < m; ++i) {
  26.             strs = reader.readLine().split(" ");
  27.             lines[i] = new Line(Integer.parseInt(strs[0]), Integer.parseInt(strs[1]), Integer.parseInt(strs[2]));
  28.         }
  29.         Arrays.sort(lines, lineComparator);
  30.         int[] ans = new int[n - 1];
  31.         int index = 0;
  32.         for (int i = 0, u, v; i < m; ++i) {
  33.             u = lines[i].u;
  34.             v = lines[i].v;
  35.             if (union(points[u], points[v])) {
  36.                 ans[index++] = i;
  37.                 if (index == n - 1) {
  38.                     break;
  39.                 }
  40.             }
  41.         }
  42.         if (index < n - 1) {
  43.             System.out.println(-1);
  44.         } else {
  45.             int sum = 0;
  46.             for (int i : ans) {
  47.                 // System.out.println(lines[i]);
  48.                 sum += lines[i].val;
  49.             }
  50.             System.out.println(sum);
  51.         }
  52.     }
  54.     private static boolean union(Point u, Point v) {
  55.         Point uMaster = u.getOrigin();
  56.         Point vMaster = v.getOrigin();
  57.         if (uMaster == vMaster) {
  58.             return false;
  59.         }
  60.         uMaster.master = vMaster;
  61.         return true;
  62.     }
  63. }
  66. class Point {
  67.     int id;
  69.     // 标识是否在同一棵树上
  70.     Point master;
  72.     public Point getOrigin() {
  73.         master = _getOrigin(this);
  74.         return master;
  75.     }
  77.     private Point _getOrigin(Point p) {
  78.         if (p != p.master) {
  79.             p.master = _getOrigin(p.master);
  80.         }
  81.         return p.master;
  82.     }
  84.     public Point(int id) {
  85.         this.id = id;
  86.         master = this;
  87.     }
  88. }
  90. class Line {
  91.     int u;
  92.     int v;
  93.     int val;
  95.     public Line(int u, int v, int val) {
  96.         this.u = u;
  97.         this.v = v;
  98.         this.val = val;
  99.     }
  101.     @Override
  102.     public String toString() {
  103.         return "Line{" +
  104.                 "u=" + u +
  105.                 ", v=" + v +
  106.                 ", val=" + val +
  107.                 '}';
  108.     }
  109. }

解法二：Prime算法

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.*;
  6. public class Main {
  7.     public static void main(String[] args) throws IOException {
  8.         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  9.         String[] strs = reader.readLine().split(" ");
  10.         final int n = Integer.parseInt(strs[0]);
  11.         final int m = Integer.parseInt(strs[1]);
  13.         Point[] points = new Point[n + 1];
  14.         for (int i = 1; i <= n; ++i) {
  15.             points[i] = new Point(i);
  16.         }
  18.         int[][] graph = new int[n + 1][n + 1];
  19.         for (int i = 1; i <= n; ++i) {
  20.             Arrays.fill(graph[i], Integer.MAX_VALUE);
  21.             graph[i][i] = 0;
  22.         }
  24.         for (int i = 0, u, v, val; i < m; ++i) {
  25.             strs = reader.readLine().split(" ");
  26.             u = Integer.parseInt(strs[0]);
  27.             v = Integer.parseInt(strs[1]);
  28.             val = Integer.parseInt(strs[2]);
  29.             graph[u][v] = val;
  30.             graph[v][u] = val;
  31.         }
  32.         for (int i = 1; i <= n; ++i) {
  33.             points[i].dis = graph[i][1];
  34.         }
  37.         List<Point> undoList = new LinkedList<>();
  38.         for (int i = 2; i <= n; ++i) {
  39.             undoList.add(points[i]);
  40.         }
  42.         int[] ans = new int[n - 1];
  43.         int index = 0;
  44.         for (int i = 0; i < n - 1; ++i) {
  45.             Point min = new Point(0);
  46.             min.dis = Integer.MAX_VALUE;
  47.             for (Point p : undoList) {
  48.                 if (p.dis < min.dis) {
  49.                     min = p;
  50.                 }
  51.             }
  52.             if (min.dis == Integer.MAX_VALUE) {
  53.                 System.out.println(-1);
  54.                 return;
  55.             }
  56.             ans[index++] = min.dis;
  57.             int minIndex = min.id;
  58.             for (Iterator<Point> iter = undoList.iterator(); iter.hasNext(); ) {
  59.                 Point tmp = iter.next();
  60.                 if (tmp.equals(min)) {
  61.                     iter.remove();
  62.                 } else {
  63.                     tmp.dis = Math.min(tmp.dis, graph[minIndex][tmp.id]);
  64.                 }
  65.             }
  66.         }
  68.         int sum = 0;
  69.         for (int i : ans) {
  70.             sum += i;
  71.         }
  72.         System.out.println(sum);
  73.     }
  74. }
  76. class Point {
  77.     int id;
  79.     int dis;
  81.     public Point(int id) {
  82.         this.id = id;
  83.         dis = 0;
  84.     }
  86.     @Override
  87.     public boolean equals(Object o) {
  88.         if (this == o) return true;
  89.         if (o == null || getClass() != o.getClass()) return false;
  90.         Point point = (Point) o;
  91.         return id == point.id;
  92.     }
  93. }

解法三：Prime算法+堆优化

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.*;
  6. public class Main {
  7.     public static void main(String[] args) throws IOException {
  8.         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  9.         String[] strs = reader.readLine().split(" ");
  10.         final int n = Integer.parseInt(strs[0]);
  11.         final int m = Integer.parseInt(strs[1]);
  12.         Point[] points = new Point[n + 1];
  13.         for (int i = 1; i <= n; ++i) {
  14.             points[i] = new Point(i);
  15.         }
  16.         for (int i = 0, u, v, val; i < m; ++i) {
  17.             strs = reader.readLine().trim().split(" ");
  18.             u = Integer.parseInt(strs[0]);
  19.             v = Integer.parseInt(strs[1]);
  20.             val = Integer.parseInt(strs[2]);
  21.             points[u].nextList.add(new int[]{v, val});
  22.             points[v].nextList.add(new int[]{u, val});
  23.         }
  25.         Comparator<int[]> comparator = new Comparator<int[]>() {
  26.             @Override
  27.             public int compare(int[] o1, int[] o2) {
  28.                 return Integer.compare(o1[1], o2[1]);
  29.             }
  30.         };
  31.         Queue<int[]> queue = new PriorityQueue<>(comparator);
  32.         points[1].isVisited = true;
  33.         queue.addAll(points[1].nextList);
  35.         int[] ans = new int[n - 1];
  36.         int index = 0;
  37.         while ((!queue.isEmpty()) && (index < n - 1)) {
  38.             int[] min = queue.poll();
  39.             if (points[min[0]].isVisited) {
  40.                 continue;
  41.             }
  42.             points[min[0]].isVisited = true;
  43.             ans[index++] = min[1];
  44.             for (int[] pair:points[min[0]].nextList){
  45.                 if (!points[pair[0]].isVisited){
  46.                     queue.add(pair);
  47.                 }
  48.             }
  49.         }
  51.         if (index < n - 1) {
  52.             System.out.println(-1);
  53.         } else {
  54.             int sum = 0;
  55.             for (int i : ans) {
  56.                 // System.out.println(i);
  57.                 sum += i;
  58.             }
  59.             System.out.println(sum);
  60.         }
  61.     }
  62. }
  64. class Point {
  65.     int id;
  66.     boolean isVisited;
  67.     List<int[]> nextList;
  69.     public Point(int id) {
  70.         this.id = id;
  71.         isVisited = false;
  72.         nextList = new ArrayList<>(id);
  73.     }
  74. }