Java实现蓝桥杯算法训练 Airport Configuration

朴灿烈づ我的快乐病毒、 2023-07-25 09:41 24阅读 0赞

## 试题 算法训练 Airport Configuration ##

问题描述  
　　ACM机场是一个本地机场，对于大多数人来说，机场不是他们的终点或起点，而是中转站。机场有一个规划图。到达的大门在机场的北边（相当于空格）。出发的大门在机场的南边（也相当于空格）。两个正对着的大门距离相当于大门间的距离。每一个到达的大门只对应一个城市。每一个出发的大门也是这样。乘客到达的大门对应他们的起始城市，而出发大门对应他们的目标城市。因为这个问题，我们只需考虑转机的乘客。  
　　转机的乘客会产生机场的交通堵塞。我们已经知道某两个城市之间的平均客流量。用这些信息，有可能能降低交通堵塞。例如，Cx城到Cy城的客流量大，就可以将他们安排得很近，甚至是对位。  
　　因为花园和商店无法穿越，所以到达门G1和出发们G3（见图）的距离为1+2=3。  
　　你需要计算几个方案的客流指数。两个大门间的客流指数等于人数乘以距离。而总的客流指数就是所有门之间的客流指数之和。

输入格式  
　　输入文件有多组测试数据。  
　　最后一组只有一个0。  
　　每组测试数据的输入有两部分。先是客流数据，之后是机场布局。  
　　数据开始时一个n(1<n<25)，表示城市数。接下来n行，每行表示一个城市的数据，第i行先是一个整数，表示起始城市，再一个1到n的整数k，表示目标城市数，k对整数，每对描述一个目标城市，第一个数是城市编号j，然后是乘客数目(最多500)从i到j的人数。  
　　机场布局部分包括1到20个方案。用一个0结束。  
　　一个方案包括3行。第一行一个数表示编号，第二行是1-n的一个排列，描述到达门对应的城市的排列，第三行用同样的方式描述出发大门。  
输出格式  
　　对于每个测试数据，输出包括一个表格，表示方案编号和客流指数，按照客流指数升序输出。若客流指数相同，则编号小的排在前面。见样例。注意方案编号右对齐，而客流指数左对齐。（样例输出前面4个空格，后面9个空格，然后没有空格，详见未格式化的试题。

样例输入
    3
    1 2 2 10 3 15
    2 1 3 10
    3 2 1 12 2 20
    1
    1 2 3
    2 3 1
    2
    2 3 1
    3 2 1
    0
    2
    1 1 2 100
    2 1 1 200
    1
    1 2
    1 2
    2
    1 2
    2 1
    0
    0
    样例输出
    Configuration Load
    2 119
    1 122
    Configuration Load
    2 300
    1 600

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main { 
    	  public static void main(String[] args) { 
    	        Scanner s=new Scanner(System.in);
    
    	        Node [][]airpot;
    	        PlanResult []plans;
    	        int [][]layout;
    	        //是否连续出现了两个0
    	        boolean repeat=false;
    	        int k;
    
    	        int n = s.nextInt();
    	        while (!repeat) { 
    	            airpot =new Node[n+1][n+1];
    	            layout=new int[2][n];
    	            plans=new PlanResult[21];
    	            k=0;
    
    	            for (int i = 0; i <n ; i++) { 
    	                //起始城市
    	                int startCity=s.nextInt();
    	                int m = s.nextInt();
    	                for (int j = 0; j < m; j++) { 
    	                    int arriveCity=s.nextInt();
    	                    Node node = new Node();
    	                    node.number=s.nextInt();
    	                    airpot[startCity][arriveCity]=node;
    	                }
    	            }
    
    
    	            //计划编号
    	            int planNumber=s.nextInt();
    	            while (planNumber != 0) { 
    	                PlanResult result=new PlanResult();
    	                result.planNumber=planNumber;
    
    	                //输入机场布局
    	                for (int i = 0; i < 2; i++) { 
    	                    for (int j = 0; j <n ; j++) { 
    	                        layout[i][j]=s.nextInt();
    	                    }
    	                }
    
    
    
    	                //计算节点距离
    	                for (int i = 0; i <n ; i++) { 
    	                    int startCity=layout[0][i];
    	                    for (int j = 0; j <n ; j++) { 
    	                        int endCity=layout[1][j];
    	                        Node node = airpot[startCity][endCity];
    	                        if (node != null) { 
    	                            node.distance=Math.abs(i-j)+1;
    	                        }
    	                    }
    	                }
    
    	                //计算机场总流量
    	                int flow=0;
    	                for (int i = 1; i <=n; i++) { 
    	                    for (int j = 1; j <=n ; j++) { 
    	                        Node node = airpot[i][j];
    	                        if (node != null) { 
    	                                flow+=node.distance*node.number;
    	                        }
    	                    }
    	                }
    	                result.flow=flow;
    	                plans[k++]=result;
    	                planNumber=s.nextInt();
    	            }
    
    	            Arrays.sort(plans,0,k);
    
    	            System.out.println("Configuration Load");
    	            for (int i = 0; i < k; i++) { 
    	                PlanResult plan = plans[i];
    	                System.out.printf("%4d%9d\n",plan.planNumber,plan.flow);
    	            }
    
    	            n=s.nextInt();
    	            if (n == 0) {  repeat=true; }
    	        }
    
    	    }
    	}
    
    	class Node { 
    	    //距离
    	    int distance;
    	    //数量
    	    int number;
    	}
    
    	class PlanResult implements Comparable<PlanResult> { 
    	    //计划编号
    	    int planNumber;
    	    //流量
    	    int flow;
    
    	    @Override
    	    public int compareTo(PlanResult planResult) { 
    	        if (Integer.compare(flow, planResult.flow)==0) { 
    	            return Integer.compare(planNumber, planResult.planNumber);
    	        }
    	        return Integer.compare(flow, planResult.flow);
    	    }
    }