問題描述： 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 }

?

轉載于:https://www.cnblogs.com/orangecyh/p/10268829.html

總結

以上是生活随笔為你收集整理的ALGO-162——Airport Configuration的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。