正文

algo-162——airportconfiguration(代码片段)

orangecyh  orangecyh  2023-02-23  758

关键词：

问题描述：

　　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

问题分析：

模拟题，没啥分析

代码：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int n;            //城市数量 
 8 int city[26][26];    //城市之间人数矩阵 
 9 int cityFrom[26];    //到达的门分布 
10 int cityTo[26];        //去向的门分布 
11 int ans[21];        //机场分布方案对应的客流指数 
12 int arrange[21];    //机场分布方案的编号输出的顺序 
13 int Count;    //测试的机场分布的数量 
14 
15 void Sort()
16     int temp;
17     for(int i=1;i<=Count;i++)
18         for(int j=1;j<=Count-i;j++)
19             if(ans[j]>ans[j+1])
20                 temp=ans[j];
21                 ans[j]=ans[j+1];
22                 ans[j+1]=temp;
23                 temp=arrange[j];
24                 arrange[j]=arrange[j+1];
25                 arrange[j+1]=temp;
26             
27         
28     
29 
30 
31 int main()    
32     while(cin>>n&&n)
33         for(int i=1;i<=20;i++)
34             arrange[i]=i;
35          
36         memset(city,0,sizeof(city));
37         memset(cityFrom,0,sizeof(cityFrom));
38         memset(cityTo,0,sizeof(cityTo));
39         memset(ans,0,sizeof(ans));
40         int from,to; //出发城市编号、目的地城市编号
41         int m;        //每行第3个数字，目的地城市数量 
42         for(int i=1;i<=n;i++)
43             cin>>from;
44             cin>>m;
45             for(int j=1;j<=m;j++)
46                 cin>>to;
47                 cin>>city[from][to];
48             
49          
50         int c;            //机场分布编号
51         Count=0;
52         while(cin>>c&&c)
53             for(int i=1;i<=n;i++)
54                 cin>>cityFrom[i];
55              
56             for(int i=1;i<=n;i++)
57                 cin>>cityTo[i];
58             
59             for(int i=1;i<=n;i++)
60                 for(int j=1;j<=n;j++)
61                     if(city[cityFrom[i]][cityTo[j]])
62                         ans[c]+=city[cityFrom[i]][cityTo[j]]*(1+abs(i-j));
63                     
64                 
65             
66             Count++; 
67         
68         cout<<"Configuration Load"<<endl;
69         Sort();        //排序 
70         for(int i=1;i<=Count;i++)
71             cout<<arrange[i]<<" "<<ans[i]<<endl;
72          
73     
74     return 0;
75