Java实现蓝桥杯算法提高最小方差生成树

1 问题描述

给定带权无向图，求出一颗方差最小的生成树。

输入格式

输入多组测试数据。第一行为N,M，依次是点数和边数。接下来M行，每行三个整数U,V,W，代表连接U,V的边，和权值W。保证图连通。n=m=0标志着测试文件的结束。

输出格式

对于每组数据，输出最小方差，四舍五入到0.01。输出格式按照样例。

样例输入

4 5

1 2 1

2 3 2

3 4 2

4 1 1

2 4 3

4 6

1 2 1

2 3 2

3 4 3

4 1 1

2 4 3

1 3 3

0 0

样例输出

Case 1: 0.22

Case 2: 0.00

数据规模与约定

1<=U,V<=N<=50,N-1<=M<=1000,0<=W<=50。数据不超过5组。

2 解决方案

本题主要考查Kruskal算法，其中的重点在于并查算法的应用，在寻找最小平方差的最小生成树时，需要枚举边权值的均值。

但是，依照这样的方法，在蓝桥练习系统中测评一直为50分，在网上找了一下其他网友写的C代码，提交也是50分，可能是蓝桥练习系统的后台测试数据有点问题，也有可能是本题枚举的精确度不够。

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.Scanner;

public class Main {

    public static int n, m;

    public static double minV;  //输入所有边中权值最小的边

    public static double maxV;  //输入所有边中权值最大的边

    public static int[] id;

    public static ArrayList<edge> map;

    public static ArrayList<Double> result = new ArrayList<Double>();

    class MyComparator implements Comparator<edge> {

        public int compare(edge arg0, edge arg1) {

            if(arg0.w > arg1.w)

                return 1;

            else if(arg0.w < arg1.w)

                return -1;

            return 0;

        }

    }

    static class edge {

        public int a;  //边的起点

        public int b;  //边的终点

        public double v;  //边的权值

        public double w;  //边权的方差值

        public edge(int a, int b, double v) {

            this.a = a;

            this.b = b;

            this.v = v;

            this.w = 0;

        }

    }

    public void init() {

        minV = Double.MAX_VALUE;

        maxV = Double.MIN_VALUE;

        map = new ArrayList<edge>();

    }

    public int find(int a) {

        int root = a;

        while(id[root] >= 0) {

            root = id[root];

        }

        int k = a, i;

        while(k != root) {

            i = id[k];

            id[k] = root;

            k = i;

        }

        return root;

    }

    public void union(int a, int b) {

        int rootA = find(a);

        int rootB = find(b);

        if(rootA == rootB)

            return;

        int num = id[rootA] + id[rootB];

        if(id[rootA] < id[rootB]) {

            id[rootB] = rootA;

            id[rootA] = num;

        } else {

            id[rootA] = rootB;

            id[rootB] = num;

        }

    }

    public void getResult() {

        double avg = minV;

        double minResult = Double.MAX_VALUE;

        for(;avg <= maxV;avg = avg + 0.3) {  //此处是解决本题的关键，即枚举最小生成树的边权的均值

            for(int i = 0;i < map.size();i++) {

                double v = map.get(i).v - avg;

                map.get(i).w = v * v;

            }

            Collections.sort(map, new MyComparator());

            id = new int[n + 1];

            for(int i = 1;i <= n;i++)

                id[i] = -1;

            double sum = 0;

            double[] value = new double[n - 1];

            int count = 0;

            for(int i = 0;i < map.size();i++) {

                int rootA = find(map.get(i).a);

                int rootB = find(map.get(i).b);

                if(rootA != rootB) {

                    union(map.get(i).a, map.get(i).b);

                    value[count++] = map.get(i).v;

                    sum += map.get(i).v;

                    if(count == n - 1)

                        break;

                }

            }

            sum = sum / (n - 1);

            double temp = 0;

            for(int i = 0;i < value.length;i++) {

                temp = temp + (value[i] - sum) * (value[i] - sum);

            }

            temp = temp / (n - 1);

            if(minResult > temp)

                minResult = temp;

        }

        result.add(minResult);

    }

    public static void main(String[] args) {

        Main test = new Main();

        Scanner in = new Scanner(System.in);

        while(true) {

            n = in.nextInt();

            m = in.nextInt();

            if(n == 0 || m == 0)

                break;

            test.init();

            for(int i = 1;i <= m;i++) {

                int a = in.nextInt();

                int b = in.nextInt();

                double v = in.nextDouble();

                map.add(new edge(a, b, v));

                minV = Math.min(minV, v);

                maxV = Math.max(maxV, v);

            }

            test.getResult();

        }

        for(int i = 0;i < result.size();i++) {

            System.out.print("Case "+(i+1)+": ");

            System.out.printf("%.2f", result.get(i));

            System.out.println();

        }

    }

}

巴特西

Java实现蓝桥杯算法提高最小方差生成树

最新文章

热门文章

巴特西

Java实现 蓝桥杯 算法提高最小方差生成树

最新文章

热门文章

Java实现蓝桥杯算法提高最小方差生成树