当前位置:首页 » Project Euler » 详细页

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.

    ABCDEFG
A-161221---
B16--1720--
C12--28-31-
D211728-181923
E-20-18--11
F--3119--27
G---231127-

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.


Solution

在加权连通图中寻找最小生成树问题。先求出原始路径矩阵中的总权重oldWeight,再通过最小生成树算法求得最小连通权重newWeight,然后oldWeight-newWeight即为冗余的边的权重。 最小生成树:搜索加权连通图,在搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点,且其所有边的权值之和亦为最小,那么这颗树称为该加权连通图的最小生成树。又称最小权重生成树。 常用的最小生成树算法有Prim算法,Kruskal算法,这里我们采用Kruskal算法。 Kruskal算法简单描述: 1. 记Graph中有v个顶点,e个边 2. 新建图Graphnew,Graphnew中拥有原图中相同的e个顶点,但没有边 3. 将原图Graph中所有e个边按权值从小到大排序 4. 循环:从权值最小的边开始遍历每条边,直至图Graph中所有的节点都在同一个连通分量中。 在本题中,算法主要分为两步: 1. 从txt文档中读取路径权重数组,计算oldWeight。 1.1 读文件到权重矩数组weights,weights[i][j]表示从顶点i到顶点j的路径权重。 - 按行读取,注意每个权重都是通过逗号','分开的,所以分割后,先把每行数据保存到字符串数组weight中。然后再将weight数组转为整型数组weights,方便后面的权重计算。 - weight中包含了'-',表示不可达到。因此在把weight数组转为weights数组时,要处理'-',在程序里,把'-'替换为整数的最大值,详见strArr2IntArr方法。 1.2 计算oldWeight - 遍历路径权重数组weights,如果权重不为最大整数,则把所有权重相加得到oldWeight。 2. 通过Kruskal算法计算newWeight。 2.1 首先设置当前顶点i是已连通的,从顶点i出发,找到下一个连通点j。 - 连通点j要满足的条件:点j是未连通的;点i和点j之间存在路径,即weights[i][j]不等于最大整数;并且weights[i][j]是点i到其他未联通的点权重中最小的;。 2.2 重新计算连通路径的权重。直到所有的点都在连通图中。

Code

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 [][] weights=ReadData();//读取数据
		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;
	}
	//从文件中读取数据
	public static int[][] ReadData()
	{
		//p107_network.txt位于电脑中的路径
		String path="C:\\Users\\wby\\Desktop\\p107_network.txt";
		int index = 0;
        BufferedReader br = null;
        List<String> lines; 
        int [][] weights=new int[1][1];
		try {
	        lines = Files.readAllLines(Paths.get(path), StandardCharsets.UTF_8); //文件的总行数
	        weights=new int[lines.size()][];//初始化weights大小
	        BufferedReader reader = new BufferedReader(new InputStreamReader(  
                    new FileInputStream(path), "utf8"));  
            String str = "";  
            int i=0;
            while ((str = reader.readLine()) != null) {  
	        	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