MX是世界上第一大传媒娱乐企业，该公司数十年的经营历史中创作了很多经典影片，此外还经营着很多的规模十分宏大世界级的主题娱乐公园。最近MX公司刚和C国X城市达成协定，共同投资建设C国国内唯一一家主题娱乐公园。
主题公园的经营管理部门计划布设m个固定的快餐饮品供应点为游客服务。希望游客游园时，绝对不要受到快餐店补货车工作运行的影响，最好的办法就是绝对不让游客在园中看到补货车，绝对不让游客听到补货车的声音。让游客觉得在园中任何一个餐饮点随时都能买到食品和饮品，能得到无穷无尽的食品和饮品。因此设计团队想把给m个餐饮点供货的通道设置在地下，并在通道内部敷设一定的隔音材料，可是修造地下供货通道的经济代价与通道总长度成正比（每100米修造代价是M万元），花费将是非常巨大的，不过游客至上。
现在设计团队手中已经有了m个餐饮点的坐标位置（x，y）信息，你是设计团队的一员，团队交给你的工作就是规划一个地下通道建设方案，将m个餐饮点都连接起来且总修造代价尽可能地小。
随机生成m个坐标信息验证你的算法和程序，如果最终程序求解的通道规划方案不唯一，则输出其中的任一方案即可（要求m>=30）。
解题代码如下，注释的较为清楚，不在过多阐述。
import java.util.Random; public class MyPrim { public static void main(String[] args) { Random random = new Random(); //随机生成m个坐标信息 int m = random.nextInt(30) + 30; // int m = 5; System.out.println("current size = " + m); //每个店铺与其他店铺的距离 int[][] map = new int[m][m]; for (int i = 0; i < m; i++) { //当前店铺与之后的所有店铺距离 for (int j = i; j < m; j++) { if (i == j) { map[i][j] = 0; } else { //每个餐饮店最少隔100米 map[i][j] = random.nextInt(400) + 100; } } //把之前的店铺距离赋值给当前店铺 for (int j = 0; j < i; j++) { map[i][j] = map[j][i]; } } System.out.println(toString(map)); //输出最短距离 System.out.println(startPrim(map, m)); } private static int startPrim(int[][] map, int m) { //总距离 int sumDistance = 0; //已经选择过的餐饮店 int[] selectedMap = new int[m]; //默认都没访问过标记为-1 for (int i = 0; i < m; i++) { selectedMap[i] = -1; } //起点默认为第一个，访问标记为0 selectedMap[0] = 0; //记录求解的通道规划方案 int startM = 0; int endM = 0; //遍历除了第一个之后的每个店铺 for (int i = 0; i < m - 1; i++) { //当前店铺的最近距离 int minDistance = Integer.MAX_VALUE; int minMIndex = -1; //遍历已经选择过得餐饮店 for (int j = 0; j < m; j++) { if (selectedMap[j] == 0) { //开始寻找与该店最近的店 int[] currentM = new int[m]; //得到该店与其他未被选择的店的距离 for (int k = 0; k < m; k++) { if (selectedMap[k] != 0) { //把二维数组里第j行的数据赋值给当前店铺 currentM[k] = map[j][k]; } else { currentM[k] = 0; } } //寻找最小值 for (int k = 0; k < m; k++) { //如果距离不为0，且最小距离大于当前距离 if (currentM[k] != 0 && minDistance > currentM[k]) { //设置最小距离为当前距离 minDistance = currentM[k]; //记录店铺下标 minMIndex = k; //记录方案 startM = j; endM = k; } } //当前这个选择过的餐饮店铺的最近距离店铺找出来后，继续循环找下一个的，直到循环完毕后找到最小的那个店铺 } } //设置minMIndex为已选择餐饮店 selectedMap[minMIndex] = 0; //总距离计算 sumDistance += minDistance; //输出方案 System.out.println("m" + startM + " is connected to m" + endM+", min distance is "+minDistance+", position["+startM+", "+endM+"]"); } return sumDistance; } //输出所有店铺的距离信息 static String toString(int[][] map) { StringBuilder s = new StringBuilder(); for (int[] ints : map) { for (int j = 0; j < ints.length; j++) { if ((j + 1) == ints.length) s.append(ints[j]).append("\n"); else s.append(ints[j]).append(" "); } } return s.toString(); } }
