中山网页网站设计模板,庆阳网站设计制作,wordpress 搜索引索,网站建站第十四课目录 1 问题描述 2 解决方案 1 问题描述 问题描述给定带权无向图#xff0c;求出一颗方差最小的生成树。输入格式输入多组测试数据。第一行为N,M#xff0c;依次是点数和边数。接下来M行#xff0c;每行三个整数U,V,W#xff0c;代表连接U,V的边#xff0c;和权值W。保证图… 目录 1 问题描述 2 解决方案 1 问题描述 问题描述 给定带权无向图求出一颗方差最小的生成树。 输入格式 输入多组测试数据。第一行为N,M依次是点数和边数。接下来M行每行三个整数U,V,W代表连接U,V的边和权值W。保证图连通。nm0标志着测试文件的结束。 输出格式 对于每组数据输出最小方差四舍五入到0.01。输出格式按照样例。 样例输入 4 51 2 12 3 23 4 24 1 12 4 34 61 2 12 3 23 4 34 1 12 4 31 3 30 0 样例输出 Case 1: 0.22Case 2: 0.00 数据规模与约定 1U,VN50,N-1M1000,0W50。数据不超过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 ArrayListedge map;public static ArrayListDouble result new ArrayListDouble();class MyComparator implements Comparatoredge {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 ArrayListedge();}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 (i1): );System.out.printf(%.2f, result.get(i));System.out.println();}}
} 转载于:https://www.cnblogs.com/liuzhen1995/p/6786554.html
