题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

Java 代码

// Don't place your source in a package
import java.text.DecimalFormat;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;








// Please name your class Main
public class Main {
    static FastScanner fs=new FastScanner();
    static class FastScanner {//scanner from SecondThread
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int Int() {
            return Integer.parseInt(next());
        }

        long Long() {
            return Long.parseLong(next());
        }

        String Str(){
            return next();
        }
    }


    public static void main (String[] args) throws java.lang.Exception {
        PrintWriter out = new PrintWriter(System.out);
        int T=1;
        for(int t=0;t<T;t++){
            int n=Int();int m=Int();
            int A[][]=new int[m][3];
            for(int i=0;i<m;i++){
                A[i][0]=Int()-1;
                A[i][1]=Int()-1;
                A[i][2]=Int();
            }
            Sol sol=new Sol();
            sol.solution(out,A,n);
        }
        out.flush();

    }

    public static int Int(){
        return fs.Int();
    }
    public static long Long(){
        return fs.Long();
    }
    public static String Str(){
        return fs.Str();
    }

}



class Sol{
    List<int[]>g[];//graph
    boolean visit1[];
    int lca[][];
    int mx1[][];int mx2[][];
    int dep[];

    public void solution(PrintWriter out,int A[][],int n){
        sort(A);
        long cost=0;long res=Long.MAX_VALUE;
        int nums[]=new int[n];
        boolean visit[]=new boolean[A.length];
        visit1=new boolean[A.length];
        g=new ArrayList[n];dep=new int[n];
        lca=new int[n][18];
        mx1=new int[n][18];mx2=new int[n][18];


        for(int i=0;i<nums.length;i++){
            nums[i]=i;
            g[i]=new ArrayList<>();
            Arrays.fill(lca[i],-1);
        }



        for(int i=0;i<A.length;i++){
            int p[]=A[i];
            int u=p[0],v=p[1],w=p[2];
            int r1=find(nums,u),r2=find(nums,v);
            if(r1!=r2){
                visit[i]=true;
                nums[r1]=r2;
                cost+=w;
                g[u].add(new int[]{v,w});
                g[v].add(new int[]{u,w});
            }
        }

        visit1[0]=true;
        dfs(0,0);


        //construct binary lifting
        for(int i=1;i<lca[0].length;i++){
            for(int j=0;j<n;j++){
                if(lca[j][i-1]==-1||lca[lca[j][i-1]][i-1]==-1)continue;
                lca[j][i]=lca[lca[j][i-1]][i-1];
                mx1[j][i]=Math.max(mx1[j][i-1],mx1[lca[j][i-1]][i-1]);
                mx2[j][i]=update(mx1[j][i],mx2[j][i-1],mx1[lca[j][i-1]][i-1],mx2[lca[j][i-1]][i-1]);

            }
        }


        for(int i=0;i<A.length;i++){
            if(visit[i])continue;
            int p[]=A[i];
            int u=p[0],v=p[1],w=p[2];
            if(u==v)continue;

            int maxCost[]=lcaq(u,v);
            int a=maxCost[0];
            int b=maxCost[1];
            long newcost1=cost-a+w;
            long newcost2=cost-b+w;

            if(newcost1>cost){
                res=Math.min(res,newcost1);
            }
            if(newcost2>cost){
                res=Math.min(res,newcost2);
            }
        }
        out.println(res);

    }

    public int[] lcaq(int x,int y){
        if(dep[x]<dep[y]){//x is deeper than y
            return lcaq(y,x);
        }

        int heap[]=new int[]{0,0};

        for(int i=17;i>=0;i--){//x is same level as y
            if(lca[x][i]==-1)continue;
            if ((dep[x]-(1<<i))>=dep[y]){
                add(heap,mx2[x][i]);
                add(heap,mx1[x][i]);
                x=lca[x][i];
            }
        }
        if(x==y)return heap;
        for(int i=17;i>=0;i--){
            if(lca[x][i]==-1)continue;
            if(lca[x][i]!=lca[y][i]){
                add(heap,mx1[x][i]);add(heap,mx1[y][i]);
                add(heap,mx2[x][i]);add(heap,mx2[y][i]);
                x=lca[x][i];
                y=lca[y][i];
            }
        }
        add(heap,mx1[x][0]);add(heap,mx1[y][0]);
        add(heap,mx2[x][0]);add(heap,mx2[y][0]);
        return heap;
    }

    public void add(int heap[],int a){
        if(a==heap[0]||a==heap[1])return;
        if(a>heap[0]){
            int old=heap[0];
            heap[0]=a;
            heap[1]=old;
        }
        else if(a>heap[1]){
            heap[1]=a;
        }
    }

    public void dfs(int root,int level){
        dep[root]=level;
        List<int[]>childs=g[root];
        for(int next[]:childs){
            int u=next[0];int w=next[1];
            if(!visit1[u]){
                visit1[u]=true;
                lca[u][0]=root;
                mx1[u][0]=w;
                mx2[u][0]=w;
                dfs(u,level+1);
            }
        }
    }

    public int find(int nums[],int x){
        if(nums[x]==x)return x;
        int root=find(nums,nums[x]);
        nums[x]=root;
        return root;
    }

    public void sort(int A[][]){
        PriorityQueue<int[]>pq=new PriorityQueue<>((a,b)->{
            return a[2]-b[2];
        });
        for(int p[]:A)pq.add(p);
        for(int i=0;i<A.length;i++){
            A[i]=pq.poll();
        }
    }

    public int update(int a,int b,int c,int d){
        if(a==b&&a==c&&a==d)return a;
        int A[]=new int[]{a,b,c,d};
        Arrays.sort(A);
        if(A[3]==A[2]){
            if(A[2]==A[1])return A[0];
            else return A[1];
        }
        return A[2];
    }
}