### Minimal network题号：107 难度： 35 中英对照

The following undirected network consists of seven vertices and twelve edges with a total weight of 243.

The same network can be represented by the matrix below.

 A B C D E F G A - 16 12 21 - - - B 16 - - 17 20 - - C 12 - - 28 - 31 - D 21 17 28 - 18 19 23 E - 20 - 18 - - 11 F - - 31 19 - - 27 G - - - 23 11 27 -

However, it is possible to optimise the network by removing some edges and still ensure that all points on the network remain connected. The network which achieves the maximum saving is shown below. It has a weight of 93, representing a saving of 243 − 93 = 150 from the original network.

Using network.txt (right click and 'Save Link/Target As...'), a 6K text file containing a network with forty vertices, and given in matrix form, find the maximum saving which can be achieved by removing redundant edges whilst ensuring that the network remains connected.

### Code

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.List;

public class p107 {
public static void main(String[] args) {
long start=System.nanoTime();
long result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

public static long run() {
int oldWeight=OldWeight(weights);//计算原始矩阵的所有路径之和
int newWeight=Kruskal(weights);//计算最小生成树中路径之和
return (long)oldWeight-newWeight;
}
//Kruskal算法
public static int Kruskal(int [][]weights)
{
int vertices=weights.length;//图中顶点的数量
boolean[] reachable = new boolean[vertices];//判断顶点是否已经连通，即已经访问过
reachable[0] = true;
int newWeight = 0;
for (int i = 1; i < vertices; i++) {
int lowestWeight = -1;
int target = -1;
//找出最短路径
for (int j = 0; j < vertices; j++) {
if (reachable[j]) {
for (int k = 0; k < vertices; k++) {
//如果点k没被访问过，点j,k之间存在权重为weights[j][k]的路径，且weights[j][k]比当前最短路径小，则k是下一个连通点
if (!reachable[k] && weights[j][k] != Integer.MAX_VALUE && (lowestWeight == -1 || weights[j][k] < lowestWeight)) {
lowestWeight = weights[j][k];//当前最短路径为weights[j][k]
target = k;//k是下一个连通点
}
}
}
}

reachable[target] = true;
newWeight += lowestWeight;//新的连通路径
}
return newWeight;
}
//计算原始图中的总的权重
public static int OldWeight(int [][] weights)
{
int oldWeight=0;
int vertices=weights.length;//图中顶点的数量
for (int i = 0; i < vertices; i++) {
for (int j = i + 1; j < vertices; j++) {
//如果存在边(i,j)，加上i,j之间的路径
if (weights[i][j] != Integer.MAX_VALUE)
oldWeight += weights[i][j];
}
}
return oldWeight;
}
//从文件中读取数据
{
//p107_network.txt位于电脑中的路径
String path="C:\\Users\\wby\\Desktop\\p107_network.txt";
int index = 0;
List<String> lines;
int [][] weights=new int[1][1];
try {
weights=new int[lines.size()][];//初始化weights大小
new FileInputStream(path), "utf8"));
String str = "";
int i=0;
String [] weight=str.split(",");
weights[i]=strArr2IntArr(weight);//把每行数据转为int后，放到weights数组里
i++;
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
return weights;
}
//String 数组转为 int 数组
public static int[] strArr2IntArr(String[] strs) {
int[] ret = new int[strs.length];
for (int i = 0; i < strs.length; i++) {
if (strs[i].equals("-")) {  //如果遇到'-'，变成最大值，表示达到不了
ret[i] = Integer.MAX_VALUE;
} else {
ret[i] = Integer.parseInt(strs[i]);
}
}
return ret;
}
}

259679
12ms