P1195口袋的天空kruskal 最小生成树 并查集 稀疏图

任彦州renyanzhou · 2019-07-01 19:11:24 · 题解

import java.util.Scanner;

        import java.util.ArrayList;
        import java.util.Collections;
        import java.util.List;
        import java.util.Scanner;
        public class Main{
            static int n;
            static int m;
            static int[]parent;
            static int[]rank;
        //  static int a,b,c;
            static int num;

            public static void init() {
                for(int i=1;i<=n;i++) {
                    parent[i]=-1;
                    rank[i]=0;
                }
            }
            public static int find_root(int x) {
                int x_root=x;
                while(parent[x_root]!=-1) {
                    x_root=parent[x_root];
                }
                return x_root;
            }
            public static int union(int x,int y) {
                int x_root=find_root(x);
                int y_root=find_root(y);
                if(x_root==y_root)return 0;
                else {
                    if(rank[x_root]>rank[y_root]) {
                        parent[y_root]=x_root;
                    }
                    else if(rank[x_root]<rank[y_root]) {
                        parent[x_root]=y_root;
                    }
                    else {
                        parent[x_root]=y_root;
                        rank[y_root]++;
                    }
                    return 1;
                }
            }
            public static void main(String[] args) {
                Scanner in=new Scanner(System.in);
                n=in.nextInt();
                m=in.nextInt();
                num=in.nextInt();
                parent=new int[n+1];
                rank=new int[n+1];
                init();
                List<xi>list=new ArrayList<xi>();
                for(int i=0;i<m;i++) {
                    list.add(new xi(in.nextInt(),in.nextInt(),in.nextInt()));
                }
                Collections.sort(list);
                int k=0;
                int sum=0;
                for(int i=0;i<m;i++) {
                    if(k==n-num)break;
                    if(union(list.get(i).f,list.get(i).t)==1) {
                        k++;
                        sum+=list.get(i).quan;
                    }
                }
                if(k==n-num) System.out.println(sum);
                else System.out.println("No Answer");
            }

        }
        class xi implements java.lang.Comparable<xi>{
            int f;
            int t;
            int quan;
            public int compareTo(xi o) {
                return this.quan-o.quan;
            }

            public xi(int f, int t, int quan) {
                super();
                this.f = f;
                this.t = t;
                this.quan = quan;
            }

        }