首页 > 代码库 > 算法笔记_164:算法提高 最小方差生成树(Java)
算法笔记_164:算法提高 最小方差生成树(Java)
目录
1 问题描述
2 解决方案
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
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
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 = http://www.mamicode.com/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(); } } }
算法笔记_164:算法提高 最小方差生成树(Java)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。