题目描述

$\text{ACM Airlines}$ 航空公司以 $\text{von Neumann}$ 机场作为枢纽机场。该机场采用走廊式布局：到达登机口均匀排列在走廊北侧，出发登机口均匀排列在走廊南侧。相邻两个登机口的距离等于走廊的宽度。每个到达登机口和出发登机口都唯一分配给一个城市。

中转乘客从出发城市的到达登机口进入航站楼，然后前往目的城市的出发登机口转机。由于机场内有商店和花园，不能斜穿走廊，因此从到达登机口 $G_i$ 到出发登机口 $G_j$ 的距离为 $|i-j|+1$。

人流负荷定义为：乘客人数 × 到达口与出发口之间的距离。总人流负荷为所有出发城市到目的城市的人流负荷之和。

输入包含多个测试用例，每个测试用例给出城市间的乘客流量数据，以及若干种登机口分配方案（配置）。需要计算每种配置的总人流负荷，并按负荷升序输出配置编号和负荷，负荷相同时配置编号小的优先。

---

题目分析

关键点解析

1. 距离计算
   题目的图中示例：到达口 $G1$（索引 $0$）到出发口 $G3$（索引 $2$）的距离为 $1+2=3$。
   这个距离由两部分组成：

   • 水平方向：从 $G1$ 走到 $G3$ 正下方对应的出发口，需要经过 $|0-2|=2$ 个间隔。
   • 垂直方向：从北侧到达口走到南侧出发口，需要横穿走廊，距离为 $1$。
     因此距离公式为 $|i-j|+1$。

2. 输入格式的特殊性
   交通数据部分：每行开头有一个整数 $1\dots N$，显式标识该行数据对应的出发城市编号。虽然输入通常按顺序给出，但题目规范要求必须读取该编号，不能依赖循环变量隐式确定。

3. 配置数量
   每个测试用例最多有 $20$ 个配置，$N\le 25$，因此直接模拟计算即可，无需优化。

4. 输出排序
   按总负荷升序排序，负荷相同按配置编号升序。输出时配置编号右对齐宽度为 $5$，负荷左对齐。

---

解题思路

步骤 1：读取交通数据

• 读入整数 $N$，若为 $0$ 则结束整个程序。
• 创建大小为 $(N+1)\times (N+1)$ 的乘客矩阵 passenger，使用 $1$ 基索引。
• 循环 $N$ 次（每行对应一个城市）：
  • 读入 from（出发城市编号）。
  • 读入 k（目的城市数量）。
  • 循环 $k$ 次，读入 to 和 cnt，存入 passenger[from][to] = cnt。

步骤 2：读取并处理每个配置

配置部分以单独一行 $0$ 结束。每个配置包含三行：

1. 配置编号 configId（正整数）。
2. $N$ 个整数，表示到达口分配（第 $i$ 个位置的城市编号）。
3. $N$ 个整数，表示出发口分配（第 $j$ 个位置的城市编号）。

对于每个配置：

• 建立映射 arrPos[city]：城市 $city$ 所在的到达口索引（$0$ 基）。
• 建立映射 depPos[city]：城市 $city$ 所在的出发口索引（$0$ 基）。
• 双重循环遍历所有城市对 $(from,to)$：
  • 若 passenger[from][to] > 0，则计算距离 $\text{dist}=|\text{arrPos}[from]-\text{depPos}[to]|+1$。
  • 累加负荷：totalLoad += passenger[from][to] * dist。
• 将 (configId, totalLoad) 存入结构体数组。

步骤 3：排序与输出

• 使用自定义比较函数：先按 load 升序，再按 id 升序。
• 调用 std::sort。
• 输出表头 "Configuration Load"。
• 遍历排序后的结果，按格式 printf("%5d %d\n", id, load) 输出。

---

复杂度分析

• 每个配置的计算复杂度为 $O(N^2)$，$N\le 25$，配置数 $\le 20$，因此单测试用例最多约 $20\times 25^2=12500$ 次操作，非常快。
• 空间复杂度 $O(N^2)$。

---

注意事项

1. 输入读取顺序：交通数据每行开头的 from 必须显式读取，不可省略。
2. 距离公式：$|i-j|+1$，不要误用为 $|i-j|$。
3. 多测试用例：每处理完一个测试用例，要清空配置列表，重新读取下一个。
4. 输出格式：配置编号右对齐 $5$ 位，负荷左对齐（直接 %d 即可），中间一个空格。

---

代码实现

// Airport Configuration
// UVa ID: 1000
// Verdict: Accepted
// Submission Date: 2026-04-26
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

struct Config {
    int id;
    int load;
};

bool cmp(const Config& a, const Config& b) {
    if (a.load != b.load) return a.load < b.load;
    return a.id < b.id;
}

int main() {
    int N;
    while (cin >> N && N != 0) {
        // 乘客矩阵
        vector<vector<int>> passenger(N + 1, vector<int>(N + 1, 0));
        for (int i = 1; i <= N; i++) {
            int from;
            cin >> from;
            int k; cin >> k;
            for (int t = 0; t < k; t++) {
                int to, cnt; cin >> to >> cnt;
                passenger[from][to] = cnt;
            }
        }

        vector<Config> configs;
        int configId;
        while (cin >> configId && configId != 0) {
            vector<int> arrPerm(N), depPerm(N);
            for (int i = 0; i < N; i++) cin >> arrPerm[i];
            for (int i = 0; i < N; i++) cin >> depPerm[i];

            // 映射城市 -> 到达口索引
            vector<int> arrPos(N + 1);
            for (int i = 0; i < N; i++) arrPos[arrPerm[i]] = i;

            // 映射城市 -> 出发口索引
            vector<int> depPos(N + 1);
            for (int i = 0; i < N; i++) depPos[depPerm[i]] = i;

            int totalLoad = 0;
            for (int from = 1; from <= N; from++) {
                for (int to = 1; to <= N; to++) {
                    int cnt = passenger[from][to];
                    if (cnt > 0) {
                        int dist = abs(arrPos[from] - depPos[to]) + 1;
                        totalLoad += cnt * dist;
                    }
                }
            }

            configs.push_back({configId, totalLoad});
        }

        sort(configs.begin(), configs.end(), cmp);

        cout << "Configuration Load\n";
        for (const auto& cfg : configs) {
            printf("%5d         %d\n", cfg.id, cfg.load);
        }
    }
    return 0;
}

---

总结

本题的核心在于正确理解距离计算公式，并严格按照输入格式要求读取数据。由于数据规模较小，可以直接模拟计算每种配置的总负荷，再排序输出。代码实现时需要注意：

• 显式读取每行开头的城市编号。
• 建立从城市到登机口索引的映射，以便 $O(1)$ 查找位置。
• 输出格式的右对齐控制。

掌握这些细节后，本题即可顺利通过。