算法笔记_164:算法提高 最小方差生成树(Java)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法笔记_164:算法提高 最小方差生成树(Java),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3306字,纯文字阅读大概需要5分钟。
内容图文
目录
1 问题描述
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 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; //输入所有边中权值最小的边publicstaticdouble maxV; //输入所有边中权值最大的边publicstaticint[] id; publicstatic ArrayList<edge> map; publicstatic ArrayList<Double> result = new ArrayList<Double>(); class MyComparator implements Comparator<edge> { publicint compare(edge arg0, edge arg1) { if(arg0.w > arg1.w) return 1; elseif(arg0.w < arg1.w) return -1; return 0; } } staticclass edge { publicint a; //边的起点publicint b; //边的终点publicdouble v; //边的权值publicdouble w; //边权的方差值public edge(int a, int b, double v) { this.a = a; this.b = b; this.v = v; this.w = 0; } } publicvoid init() { minV = Double.MAX_VALUE; maxV = Double.MIN_VALUE; map = new ArrayList<edge>(); } publicint 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; } publicvoid 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; } } publicvoid 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 = newint[n + 1]; for(int i = 1;i <= n;i++) id[i] = -1; double sum = 0; double[] value = newdouble[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); } publicstaticvoid 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(); } } }
原文:http://www.cnblogs.com/liuzhen1995/p/6786554.html
内容总结
以上是互联网集市为您收集整理的算法笔记_164:算法提高 最小方差生成树(Java)全部内容,希望文章能够帮你解决算法笔记_164:算法提高 最小方差生成树(Java)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。