题目描述

给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。

由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树。

输入格式
第一行包含两个整数n和m。

接下来m行，每行包含三个整数u，v，w，表示点u和点v之间存在一条权值为w的边。

输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

数据范围
1≤n≤105,
1≤m≤2∗105,
图中涉及边的边权的绝对值均不超过1000。

输入样例：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

输出样例：

6

算法1

构造最小生成树的算法主要有：克鲁斯卡尔（Kruskal）算法和普利姆（Prim）算法他们都遵循以上准则。

克鲁斯卡尔算法的基本思想是以边为主导地位，始终选择当前可用（所选的边不能构成回路）的最小权植边。所以Kruskal算法的第一步是给所有的边按照从小到大的顺序排序。这一步可以直接使用库函数qsort或者sort。接下来从小到大依次考察每一条边（u，v）。

具体实现过程如下：

1、设一个有n个顶点的连通网络为G（V,E），最初先构造一个只有n个顶点，没有边的非连通图T={V,空}，图中每个顶点自成一格连通分量。

2、在Ｅ中选择一条具有最小权植的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入到Ｔ中；否则，即这条边的两个顶点落到同一连通分量 上，则将此边舍去（此后永不选用这条边），重新选择一条权植最小的边。

3、如此重复下去，直到所有顶点在同一连通分量上为止。

　　最关键的地方在于“连通分量的查询和合并”，需要知道任意两个点是否在同一连通分量中，还需要合并两个连通分量。这个问题正好可以用并查集完美的解决

并查集（Union-Find set）这个数据结构可以方便快速的解决这个问题。基本的处理思想是：初始时把每个对象看作是一个单顶点集合；然后依次按顺序读入连通边，将连通边中的两个顶点合并。在此过程中将重复使用一个查找（Find），确定一个集合在哪个集合中。当读入一个连通边（ｕ，ｖ）时，先判断ｕ和ｖ是否在同一个集合中，；如果不在同一集合中，把ｕ、ｖ所在集合合并，使得这两个集合中的任意两个元素都连通。因此并查集在处理时，主要用到查找和合并。

为了方便并查集的描述与实现，通常把先后加入到一个集合中的元素表示成一个树结构，并用根结点来代表这个集合。在查找的时候，如果这个结点没有父节点，说明这个结点为根节点。判断顶点a和顶点b能不能连在一起，看顶点a和顶点b是不是在同一个集合中(同一个集合表示这两个顶点通过其他的顶点已连通，如：a->c->b,a和b是连通的，不能直接将a和b连通,否则，形成环，就不能构成最小生成树)

第一组数据通过了，由于我第二组数据中的10个数据只通过了8个数据，希望大家帮忙指正

java代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static class Edge<T> implements Comparable<Edge> {
        private T start;
        private T end;
        private int distance;

        public Edge(T start, T end, int distance) {
            this.start = start;
            this.end = end;
            this.distance = distance;
        }

        public T getStart() {
            return start;
        }

        public void setStart(T start) {
            this.start = start;
        }

        public T getEnd() {
            return end;
        }

        public void setEnd(T end) {
            this.end = end;
        }

        public int getDistance() {
            return distance;
        }

        public void setDistance(int distance) {
            this.distance = distance;
        }

        @Override
        //实现边的权值从小到大进行排序
        public int compareTo(Edge obj) {
            int targetDis = obj.getDistance();
            return distance > targetDis ? 1 : (distance == targetDis ? 0 : -1);
        }
    }

    public static class UnionFind {

        public static UFNode find(UFNode x) {
            UFNode p = x;
            Set<UFNode> path = new HashSet<UFNode>();
            // 记录向上追溯的路径上的点，找到根节点，
            while (p.parent != null) {
                path.add(p);
                p = p.parent;
            }
            // 这些点的parent全部指向这个集合的代表(根节点)
            for (UFNode ppp : path) {
                ppp.parent = p;     //直接指向根节点
            }
            // root
            return p;   //找到这个顶点所在的根节点代表的集合

        }

        public static void union(UFNode x, UFNode y) {
            find(y).parent = find(x);
        }

        public static class UFNode {
            UFNode parent;
        }
    }

    private final List<Edge> edgeList;
    private final int n;// 总顶点数

    private Set<Edge> T = new HashSet<>();// 生成树的边集
    private Map pntAndNode = new HashMap();

    public Set<Edge> getT() {
        buildMST();
        return T;
    }

    public Main(List<Edge> edgeList, int n) {
        this.edgeList = edgeList;
        //初始化，每一个顶点对应一个集合， //为每个顶点建立一个并查集的集合，用map集合，使顶点与并查集的结点之间形成一种映射关系
        for (Edge edge : edgeList) {
            pntAndNode.put(edge.getStart(), new UnionFind.UFNode());
            pntAndNode.put(edge.getEnd(), new UnionFind.UFNode());
        }
        this.n = n;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Edge> l = new ArrayList<>();       
        int k = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();
        for (int i = 0; i < m; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            l.add(new Edge(a, b, c));
        }

        List<Edge> edgeList = l;
        Main obj = new Main(edgeList, k);
        // obj.buildMST();
        long sum = 0;
        //顶点个数不等于边数-1，说明没有最小生成树
        if (obj.getT().size() != k-1) {
            System.out.println("impossible");

        }else{
            //权值求和
            for (Edge e : obj.getT()) {     
                sum += e.getDistance();
           }
            System.out.println(sum);
        }
    }


    /* 构建MST的核心方法 */
    private void buildMST() {
        Collections.sort(edgeList);// 排序
        // 迭代
        for (Edge e : edgeList) {
            //如果构成一个环
            if (!ok(e))
                continue;
            // 确认过了，就把边都加入
            T.add(e);

            if (T.size() == n - 1)
                return;             // 生成树的边数==总顶点数-1 =》 形成最小生成树

        }
    }

    // 并查集中查询e 的起点和终点是否在一个集中
    private boolean ok(Edge e) {
       //
        UnionFind.UFNode x = (UnionFind.UFNode) pntAndNode.get(e.getStart());
        UnionFind.UFNode y = (UnionFind.UFNode) pntAndNode.get(e.getEnd());
        if (UnionFind.find(x) != UnionFind.find(y)) {   // 并查集的find方法，查找顶点x和y是否在同一个集和中
            UnionFind.union(x, y);   // 不在同一个集合中，不会形成环，合并，并返回true
            return true;
        }
        return false;
    }

}

参考文献

树（Tree）：如果一个无向连通图中不存在回路，则这种图称为树。

生成树 （Spanning Tree）：无向连通图G的一个子图如果是一颗包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图的极小连通子图。这里所谓极小是指：若在树中任意增加一条边，则将出现一条回路；若去掉一条边，将会使之变成非连通图。

最小生成树（Minimum Spanning Tree，MST）：或者称为最小代价树Minimum-cost Spanning Tree:对无向连通图的生成树，各边的权值总和称为生成树的权，权最小的生成树称为最小生成树。常用于网络构建等建设性问题的优化。

构成生成树的准则有三条：

1、 必须只使用该网络中的边来构造最小生成树。

2、必须使用且仅使用n-1条边来连接网络中的n个顶点

3、不能使用产生回路的边。