算法筆記_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

樣例輸出

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();}}
}

?