블 루 브리지 컵알고리즘 증가최소 분산 생 성 트 리 (Kruskal 알고리즘)

문제 설명여러 그룹의 테스트 데 이 터 를 입력 하 십시오.첫 번 째 행 위 는 N, M 으로 포인트 와 변 수 를 순서대로 한다.다음 M 줄 은 줄 마다 세 개의 정수 U, V, W 로 U, V 를 연결 하 는 변 과 가중치 W 를 대표 합 니 다.연결 을 보증 하 다.n = m = 0 은 테스트 파일 의 끝 을 표시 합 니 다.출력 형식 은 각 그룹의 데이터 에 대해 출력 최소 분산, 반올림 에서 0.01 까지 입 니 다.출력 형식 은 샘플 에 따른다.샘플 입력 451, 2, 1, 2, 3, 4, 4, 1, 2, 4, 6, 1, 2, 3, 3, 4, 1, 2, 3, 3, 3, 0 샘플 출력 케이스 1: 0.22 케이스 2: 0.00 데이터 규모 와 약정 1 & lt; = U, V & gt; = N & gt; = 50, N - 1 & lt; = M & gt; = 1000, 0 & gt; = W & gt; = 50.데이터 가 5 조 를 넘 지 않 습 니 다.

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
import java.util.function.Function;
import java.util.function.ToDoubleFunction;
import java.util.function.ToIntFunction;
import java.util.function.ToLongFunction;

/** * @author   * */
public class Main {
    private static ArrayList<Double> list=new ArrayList<Double>();

    /** * @param args */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        while(true){
            int nodeNum=sc.nextInt();
            int edgeNum=sc.nextInt();
            if(nodeNum==0&&edgeNum==0){
                break;
            }
            list.add(new Test(sc,nodeNum,edgeNum).getMinVariance());
        }
        for(int i=1;i<=list.size();i++){
            System.out.println("Case "+i+": "+new BigDecimal(list.get(i-1)).divide(BigDecimal.ONE,2,BigDecimal.ROUND_HALF_UP));
        }

    }

}
class Test{
    private int nodeNum;//    
    private int edgeNum;//   
    private ArrayList<Edge> edge=new ArrayList<Edge>();//  
    private ArrayList<Edge> Enew=new ArrayList<Edge>();//          
    private int[] root;//root[i]:  i           
    private double minVariance=Double.MAX_VALUE;//    

    public Test(Scanner sc,int nn,int en){
        init(sc,nn,en);
    }

    public double getMinVariance(){
        return minVariance; 
    }

    void init(Scanner sc,int nn,int en){
        nodeNum=nn;
        edgeNum=en;
        root=new int[nodeNum+1];

        for(int i=0;i<edgeNum;i++){
            edge.add(new Edge(sc.nextInt(),sc.nextInt(),sc.nextInt()));
        }

        Collections.sort(edge,new EdgeWeightComparator());//    weight    
        int minAverage=0;//           
        int maxAverage=0;//           
        for(int i=0;i<nodeNum-1;i++){
            minAverage+=edge.get(i).weight;
            maxAverage+=edge.get(edgeNum-1-i).weight;
        }

        for(int ave=minAverage;ave<=maxAverage;ave++){
            for(int i=0;i<edgeNum;i++){
                double temp=edge.get(i).weight-(ave*1.0)/(nodeNum-1);
                edge.get(i).cost=temp*temp;
            }
            Collections.sort(edge,new EdgeCostComparator());//    cost    
            initRoot();
            Enew.clear();
            kruskal(ave);
        }
    }

    /** Kruskal    :    WN=(V,{E})       n        ，                     ：         n    ，        ，                      ，        n        。   ，      E            ，               ，       ，     ，                   ；  ，                 ，    ，                 。    ，          ，        n-1    。 */
    void kruskal(int ave){
        for(int i=0;i<edgeNum&&Enew.size()<nodeNum-1;i++){
            Edge tempE=edge.get(i);
            if(!isInSameTree(tempE.u,tempE.v)){
                Enew.add(tempE);
                root[tempE.u]=root[tempE.v];
            }
        }

        int realAverage=0;
        double result=0;
        for(int i=0;i<nodeNum-1;i++){
            realAverage+=Enew.get(i).weight;
            result+=Enew.get(i).cost;
        }
        result=result/(nodeNum-1);
        if(realAverage==ave&&result<minVariance){
            minVariance=result;
        }
    }

    //              
    private boolean isInSameTree(int from,int to){
        if(findRoot(from)==findRoot(to)){
            return true;
        }else{
            return false;
        }
    }

    //         
    private int findRoot(int i){
        if(root[i]==i){
            return i;
        }else{
            return root[i]=findRoot(root[i]);
        }
    }

    //              root  
    private void initRoot(){
        for(int i=1;i<=nodeNum;i++){
            root[i]=i;
        }
    }


}

class Edge{
    int u;
    int v;
    int weight;//   
    int cost;//（weight-average）^2

    public Edge(int u,int v,int weight){
        this.u=u;
        this.v=v;
        this.weight=weight;
    }
}


class EdgeWeightComparator implements Comparator<Edge>{

    public int compare(Edge arg0, Edge arg1) {
        // TODO Auto-generated method stub
        return arg0.weight-arg1.weight;
    }

    public static <T, U extends Comparable<? super U>> Comparator<T> comparing(
            Function<? super T, ? extends U> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T, U> Comparator<T> comparing(
            Function<? super T, ? extends U> arg0, Comparator<? super U> arg1) {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T> Comparator<T> comparingDouble(
            ToDoubleFunction<? super T> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T> Comparator<T> comparingInt(ToIntFunction<? super T> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T> Comparator<T> comparingLong(ToLongFunction<? super T> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T extends Comparable<? super T>> Comparator<T> naturalOrder() {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T> Comparator<T> nullsFirst(Comparator<? super T> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T> Comparator<T> nullsLast(Comparator<? super T> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T extends Comparable<? super T>> Comparator<T> reverseOrder() {
        // TODO Auto-generated method stub
        return null;
    }

    public Comparator<Edge> reversed() {
        // TODO Auto-generated method stub
        return null;
    }

    public Comparator<Edge> thenComparing(Comparator<? super Edge> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public <U extends Comparable<? super U>> Comparator<Edge> thenComparing(
            Function<? super Edge, ? extends U> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public <U> Comparator<Edge> thenComparing(
            Function<? super Edge, ? extends U> arg0, Comparator<? super U> arg1) {
        // TODO Auto-generated method stub
        return null;
    }

    public Comparator<Edge> thenComparingDouble(
            ToDoubleFunction<? super Edge> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public Comparator<Edge> thenComparingInt(ToIntFunction<? super Edge> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public Comparator<Edge> thenComparingLong(ToLongFunction<? super Edge> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

}



class EdgeCostComparator implements Comparator<Edge>{

    public int compare(Edge arg0, Edge arg1) {
        // TODO Auto-generated method stub
        if(arg0.cost>arg1.cost){
            return 1;
        }else{
            return -1;
        }
    }

    public static <T, U extends Comparable<? super U>> Comparator<T> comparing(
            Function<? super T, ? extends U> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T, U> Comparator<T> comparing(
            Function<? super T, ? extends U> arg0, Comparator<? super U> arg1) {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T> Comparator<T> comparingDouble(
            ToDoubleFunction<? super T> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T> Comparator<T> comparingInt(ToIntFunction<? super T> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T> Comparator<T> comparingLong(ToLongFunction<? super T> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T extends Comparable<? super T>> Comparator<T> naturalOrder() {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T> Comparator<T> nullsFirst(Comparator<? super T> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T> Comparator<T> nullsLast(Comparator<? super T> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public static <T extends Comparable<? super T>> Comparator<T> reverseOrder() {
        // TODO Auto-generated method stub
        return null;
    }

    public Comparator<Edge> reversed() {
        // TODO Auto-generated method stub
        return null;
    }

    public Comparator<Edge> thenComparing(Comparator<? super Edge> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public <U extends Comparable<? super U>> Comparator<Edge> thenComparing(
            Function<? super Edge, ? extends U> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public <U> Comparator<Edge> thenComparing(
            Function<? super Edge, ? extends U> arg0, Comparator<? super U> arg1) {
        // TODO Auto-generated method stub
        return null;
    }

    public Comparator<Edge> thenComparingDouble(
            ToDoubleFunction<? super Edge> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public Comparator<Edge> thenComparingInt(ToIntFunction<? super Edge> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

    public Comparator<Edge> thenComparingLong(ToLongFunction<? super Edge> arg0) {
        // TODO Auto-generated method stub
        return null;
    }

}