Wonderland(Kruskal)

楽園

ワンダーランドに問題があったつまり、ワンダーランドの各道路を守る財政はすでに売り切れている.
Wonderlandは、すべての都市を接続する道路を選択し、残りの道路を閉鎖してメンテナンスコストを最小限に抑えようとしました.

上の地図は各都市が1から9まで表示され、地図の右側は最低料金196ですべての都市を接続する方法を見つけます.

説明の入力

第1行は都市の個数V(1≦V≦100)と道路の個数E(1≦E≦1000)を与える.
次のE行は、各道路の情報を表す3つの整数A、B、Cを与える.
これは、A番都市とB番都市がメンテナンス費用Cの道路でつながっていることを意味します.

出力の説明

すべての都市を接続するのに必要な最低料金を支えようとします.

入力

9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15

しゅつりょく

196

誤った実装コード

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int v = in.nextInt();
        int e = in.nextInt();

        ArrayList<Edge> list = new ArrayList<>();
        //간선 숫자 = 노드 숫자 - 1
        for(int i=0;i<e;i++){
            list.add(new Edge(in.nextInt(),in.nextInt(),in.nextInt()));
        }

        Collections.sort(list); //오름차순 정렬

        ArrayList<Integer> cycleCheck = new ArrayList<>();
        int answer = 0;

        for(Edge edge : list){
            //비용이 적은 간선부터 포함. 사이클 테이블에 포함안된 경우만 add
            if(!(cycleCheck.contains(edge.node1)&&cycleCheck.contains(edge.node2))){
                //둘다 포함이 안된 경우만 사이클 안만듦.
                if(!cycleCheck.contains(edge.node1)) cycleCheck.add(edge.node1);
                if(!cycleCheck.contains(edge.node2)) cycleCheck.add(edge.node2);
                answer += edge.price;
                System.out.println("n1 :"+edge.node1+" n2: "+edge.node2+" price: "+edge.price);
            }
        }

        System.out.println(answer);

    }

    static class Edge implements Comparable<Edge>{
        public Edge(int node1, int node2, int price) {
            this.node1 = node1;
            this.node2 = node2;
            this.price = price;
        }

        int node1;
        int node2;
        int price;

        @Override
        public int compareTo(Edge o) {
            return this.price - o.price; //간선 비용 오름차순 정렬.
        }
    }

入力:
9 12
1 2 12
1 9 25
2 3 10
2 8 40
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 35
出力:
216出て181出てくるはずです
質問:
既存のチェック条件-Edgeのノード1とノード2がチェックリストに含まれていない場合、計算されます.
この場合、すべてのノードが接続できず、disjoint setが作成される可能性があります.
union&findを使用して実現しません.

インプリメンテーションコード

 static int[] unf;
    static int find(int v){
        if(v==unf[v]) return v;
        else return unf[v]=find(unf[v]);
    }

    static void union(int a,int b){
        int fa = find(a);
        int fb = find(b);
        if(fa!=fb) unf[fa] = fb;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int v = in.nextInt();
        int e = in.nextInt();

        unf = new int[v+1];
        for(int i=1;i<=v;i++){
            unf[i] = i;
        }

        ArrayList<Edge> list = new ArrayList<>();
        int answer = 0;
        for(int i=0;i<e;i++){
            list.add(new Edge(in.nextInt(),in.nextInt(),in.nextInt()));
        }

        Collections.sort(list); //오름차순 정렬

        //간선개수 = 노드 개수 - 1
        for(Edge edge : list){
            if(find(edge.node1)!= find(edge.node2)) {
                union(edge.node1, edge.node2);
                answer += edge.price;
            }
        }

        System.out.println(answer);

    }

    static class Edge implements Comparable<Edge>{
        public Edge(int node1, int node2, int price) {
            this.node1 = node1;
            this.node2 = node2;
            this.price = price;
        }

        int node1;
        int node2;
        int price;

        @Override
        public int compareTo(Edge o) {
            return this.price - o.price; //간선 비용 오름차순 정렬.
        }
    }

union&findを使用して、各インデックスの代表ノードをチェックします.代表ノードが異なる(ループを作成しない)場合にのみ、答えに幹線値を追加します.

アルゴリズム
union&findの使用
各edge(edge 1、edge 2、price)にナビゲート
find(edge1) != find(edge 2):代表ノードが異なる場合、ループは作成されません.
answer += edge.price