「IOI2022」千岛 题解

问题分析

我们需要在满足严格约束条件下找到一条从岛屿 $0$ 出发并回到岛屿 $0$ 的路径：

$1$. 访问要求：必须访问至少一个 $0$ 以外的岛屿 2. 状态复位：所有独木舟必须回到初始位置 3. 连续使用限制：不能连续使用同一艘独木舟

关键观察

图论建模

将问题建模为有向多重图：

• 每个独木舟 $i$ 对应两条有向边：
  • 边 $e_i^+$：从 $U_i$ 到 $V_i$（初始方向）
  • 边 $e_i^-$：从 $V_i$ 到 $U_i$（反向）

约束转化

状态复位条件 ⇒ 对于每个独木舟 $i$，必须使用 $e_i^+$ 和 $e_i^-$ 各一次

连续使用限制 ⇒ 不能连续使用 $e_i^+$ 和 $e_i^-$（属于同一物理独木舟）

算法思路

核心解法：改进的欧拉回路算法

步骤1：可行性判断

检查是否存在满足以下条件的回路：

• 从节点 $0$ 出发并回到节点 $0$
• 每个独木舟的正向和反向边各使用一次
• 不连续使用同一独木舟的边

步骤2：回路构造（Hierholzer变体）

def find_eulerian_circuit():
    stack = [0]
    path = []
    last_boat = -1  # 记录上次使用的独木舟
    
    while stack:
        u = stack[-1]
        if 有可用的边且不违反连续使用限制:
            v, boat_id = 选择下一条边(u, last_boat)
            标记边为已使用
            last_boat = boat_id
            stack.append(v)
        else:
            # 回溯
            if len(path) > 0:
                记录路径信息
            stack.pop()
    
    return 调整后的路径

针对特殊子任务的解法

子任务1（N=2）：

• 只有两个岛屿，可以暴力枚举所有可能的路径组合
• 检查是否满足所有约束条件

子任务2（成对独木舟）：

• 天然的对称结构
• 可以构造形如：$0 \rightarrow A \rightarrow 0 \rightarrow B \rightarrow 0$ 的路径

子任务3-4（偶数编号成对）：

• 利用配对独木舟的结构特性
• 设计专门的交替使用策略

具体实现策略

数据结构设计

struct Edge {
    int to, boat_id;  // 目标岛屿，独木舟编号
    bool used;        // 是否已使用
    bool direction;   // 方向：true为正向，false为反向
};

vector<vector<Edge>> graph;  // 邻接表
vector<int> edge_count;      // 每个节点的出边计数

算法框架

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    // 1. 构建图结构
    build_graph(N, M, U, V);
    
    // 2. 检查可行性
    if (!is_feasible()) {
        return false;
    }
    
    // 3. 构造路径
    vector<int> path = construct_path();
    
    // 4. 验证并返回
    if (path.size() > 0 && path.size() <= 2000000) {
        return path;
    } else {
        return true;  // 部分分数
    }
}

可行性判断条件

1. 连通性：所有涉及的岛屿必须与岛屿 $0$ 连通
2. 度数平衡：对于每个节点，入度等于出度
3. 特殊约束：必须存在至少一条从 $0$ 到其他岛屿的边

路径构造技巧

处理连续使用限制

int choose_next_edge(int u, int last_boat) {
    for (auto& edge : graph[u]) {
        if (!edge.used && edge.boat_id != last_boat) {
            return edge.boat_id;
        }
    }
    // 如果没有可用边，需要特殊处理
    return -1;
}

状态复位保证

通过确保每个独木舟的正向和反向边都被使用一次来保证状态复位。

复杂度分析

• 时间复杂度：$O(N + M)$
• 空间复杂度：$O(N + M)$
• 路径长度：最多 $2M$ 次航行（每个独木舟使用两次）

示例解析

样例1

N=4, M=5
U = [0,1,2,0,3], V = [1,2,3,3,1]

解决方案：[0,1,2,4,0,3,2,1,4,3]

验证：

• 访问了岛屿 0,1,2,3,1,0,3,2,1,0
• 每个独木舟使用了正向和反向各一次
• 没有连续使用同一独木舟

样例2

N=2, M=3  
U = [0,1,1], V = [1,0,0]

不可行原因：无法让所有独木舟回到初始位置

特殊情况处理

1. 死锁情况：当必须使用某独木舟但受连续使用限制时，插入"中转"边
2. 路径优化：避免生成过长的路径（超过 2,000,000）
3. 边界情况：处理只有一个岛屿有出边的情况

算法标签

• 欧拉回路
• 图论算法
• 路径构造

实现注意事项

1. 效率优化：使用合适的数据结构快速选择下一条边
2. 内存管理：避免在大型图上使用过多内存
3. 正确性验证：确保生成的路径满足所有约束条件
4. 部分分数：当无法找到最优解时返回 true 获得部分分数

---

总结

本题的核心在于将物理约束转化为图论问题，通过改进的欧拉回路算法在满足严格限制条件下构造可行路径。关键在于： $1$. 正确的图建模 2. 可行性条件的准确判断
3. 路径构造算法的精心设计 4. 特殊约束的有效处理

对于不同规模的输入和特殊结构，可能需要采用不同的策略来获得最优解或部分分数。