蓝桥杯 Island Hopping Java代码

问题描述

　　太平洋岛网公司（PLN）已经瞄向了太平洋中的一些群岛。这些群岛没有快捷的互联网连接。PLN计划向群岛提供互联网服务，以开发这个太平洋中潜在的市场。每组群岛的核心岛屿已经被深海电缆连入互联网。接下来需要做的事把其余岛屿和核心岛屿连接起来。
　　对于每个岛，将给出它的路由器的位置和居民数量。PIN将会在群岛中连接多条电缆，每条电缆连接两座岛的路由器，最后使得每座岛都通过一条电缆路径与核心岛屿相连。PIN希望总的电缆长度最小。这样也许会有多个最佳方案。PIN并不关心哪个最佳网络方案被采纳。
　　PIN对于新顾客连上互联网的平均时间很感兴趣，我们不妨假设：所有连接网络的电线都是同时开始建设的。电缆铺设效率为一千米每天。因此，短的电缆会比长的更快铺好。
　　当一座岛到核心岛屿的电缆连通时，这座岛就接入了互联网。PIN希望你告诉他所有居民连入互联网的平均时间。

输入格式

　　输入数据包含多组群岛的描述。每组描述的第一行是一个正整数n，表示群岛的数量(n ≤ 50)。接下来n行每行包含三个整数xi,yi,mi，表示路由器的位置（xi,yi），以及岛上居民数量mi (mi > 0)。坐标以千米为单位。序列中的第一座岛是核心岛屿。
　　输入数据最后以一个整数0结束。

输出格式

　　对于测试点中的每组群岛，输出该组的序列号和居民连入互联网的平均天数。保留两位小数。具体格式如样例输出所示。
　　每一个测试点输出后打印一个空行。

样例输入

7
11 12 2500
14 17 1500
9 9 750
7 15 600
19 16 500
8 18 400
15 21 250
0

样例输出

Island Group: 1 Average 3.20

数据规模和约定

　　输入数据中所有数字保证不超过2^31-1

初读题目，不是很理解它的意思，后来才知道这题的关键就是求最小生成树。也就是说，有n个岛屿，用n-1条边将他们连接起来，并且这n-1条边的长度之和是最小的才满足题意。题目给出的n<=50，对应的图又是一个完全图，所以这是一个稠密图，适用于prim算法，不知道这个算法原理的百度一下，很多详细的讲解，学过数据结构的应该听说过这个算法。弄懂这一点，也就有了一个思考的方向。

但是求出最小生成树之后，还有一个关键点没有解决，就是每个岛屿的联网时间问题。题目说了，所有网络电线都是同时开始建设的，也就是说，n-1条电线是同时建设的，那么这时每个岛的通网最短时间怎么分析呢，这时我们就要分析两种情况。第一种是当前岛屿到它的上一个岛屿的连接时间大于上一个岛屿的通网时间（上一个岛屿在当前岛屿与核心岛屿之间，也就是说，上一个岛屿的通网时间一定小于等于当前岛屿通网时间，因为只有上一个岛屿通网之后，当前岛屿才能通网，即上一个岛屿相当于一个中间点）这时当前岛屿的通网时间就等于两岛屿的连接时间；第二种情况就是当前岛屿与上一个岛屿的连接时间小于上一个岛屿的通网时间，这时当前岛屿的通网时间等于上一岛屿的通网时间。

队列排序不清楚的可以看一下这个https://www.cnblogs.com/wei-jing/p/10806236.html

  1 import java.util.Comparator;
  2 import java.util.LinkedList;
  3 import java.util.List;
  4 import java.util.PriorityQueue;
  5 import java.util.Queue;
  6 import java.util.Scanner;
  7 
  8 
  9 public class Main {
 10     
 11     public static void main(String[] args) {
 12         
 13         Scanner scanner=new Scanner(System.in);
 14         int n=scanner.nextInt();
 15         int k=0;//表示输出第几个结果
 16         int ptotal=0;//总人数
 17         double ave=0;//平均通网时间
 18         List<Edge> resE=new LinkedList<Edge>();//保存n-1条边
 19         
 20         
 21         Comparator<Edge> cEdge=new Comparator<Edge>() {//自定义比较器，用于用于队列的排序
 22             public int compare(Edge e1,Edge e2) {
 23                 if(e1.dis>e2.dis) return 1;
 24                 if(e1.dis<e2.dis) return -1;
 25                 else return 0;
 26             }
 27         };
 28         
 29         
 30         Queue<Edge> keep=new PriorityQueue<Edge>(cEdge);//用来存储于当前节点相关的所有的边,这里用了自定义的比较器，也就是按照边长度的升序排序
 31         
 32         
 33         while(n!=0) {
 34             //一开始所有数据初始化清零
 35             resE.clear();
 36             keep.clear();
 37             k++;
 38             ave=0;
 39             ptotal=0;
 40             
 41             
 42             boolean[]visit=new boolean[n];//用来记录节点是否被访问，以免重复访问
 43             Position[]positions=new Position[n];//存储n个岛屿的信息
 44             for(int i=0;i<n;i++) {//将输入的数据存储，连接时间一开始设为0
 45                 positions[i]=new Position(scanner.nextInt(),scanner.nextInt(),scanner.nextInt(),0);
 46                 ptotal+=positions[i].pnum;//计算总人数，用于之后的算平均时间
 47             }
 48             visit[0]=true;//因为第一个点是核心岛屿，一定最先访问，将它设置为true
 49             
 50             
 51             for(int i=1;i<n;i++) {//将与当前岛屿相关联的边全部保存到keep中
 52                 double x2=Math.pow(positions[0].x-positions[i].x,2);
 53                 double y2=Math.pow(positions[0].y-positions[i].y, 2);
 54                 keep.add(new Edge(0,i, Math.sqrt(x2+y2)));
 55             }
 56             while(!keep.isEmpty()&&resE.size()!=n-1) {//当已将找到了n-1条边时，退出循环
 57             Edge e1=keep.poll();//弹出队列的队首元素，因为是按照dis的升序排序的，所以队首元素对应的dis一定是最小的
 58             if(visit[e1.to]==true)//如果该节点被访问过，重新取队首元素
 59                 continue;
 60             
 61             resE.add(e1);//将这条边加入到储存边的链表中
 62             visit[e1.to]=true;
 63             
 64             for(int i=1;i<n;i++) {//以这条边的终点为起点，在keep中加入所有与终点相关联的边
 65                 if(visit[i]==false) {//这个点一定是没有访问过的
 66                     double x2=Math.pow(positions[e1.to].x-positions[i].x, 2);
 67                     double y2=Math.pow(positions[e1.to].y-positions[i].y, 2);
 68                     keep.add(new Edge(e1.to, i, Math.sqrt(x2+y2)));
 69                 }
 70             }
 71             
 72             
 73             }
 74             for(int i=0;i<resE.size();i++) {//依次比较两岛屿的连接时间与上一岛屿通网时间(因为resE中的元素是从核心岛屿出发向外扩散的，所以上一岛屿的通网时间一定是一个确定值)
 75                 Edge now=resE.get(i);
 76                 if(now.dis>positions[now.from].time)//如果走完当前边的时间大于这条边起点的通电时间，那么这条边终点的最早通电时间为前者
 77                     positions[now.to].time=now.dis;
 78                 else 
 79                     positions[now.to].time=positions[now.from].time;
 80                 
 81             }
 82             
 83             for(int i=1;i<n;i++) {
 84                 ave+=positions[i].time/ptotal*positions[i].pnum;//先除再乘，防溢出
 85             }
 86             System.out.print("Island Group: "+k+" Average ");
 87             System.out.println(String.format( "%.2f",ave));
 88             System.out.println("");
 89             n=scanner.nextInt();
 90         }
 91         
 92         
 93     }
 94     
 95     
 96 }
 97 class Position{//岛屿信息
 98     int x,y;//坐标
 99     int pnum;//人数
100     double time;//通网时间
101     public Position(int x,int y,int pnum,double time) {
102         this.x=x;
103         this.y=y;
104         this.pnum=pnum;
105         this.time=time;
106     }
107 }
108 
109 class Edge {//边信息
110     int from,to;//起点终点
111     double dis;//两点距离（也可以表示两点连接所用的时间，因为铺设效率是1Km/天）
112     public Edge(int from,int to,double dis) {
113         this.from=from;
114         this.to=to;
115         this.dis=dis;
116     }
117     
118 }