「CTSC2016」科学考察队 题解

题目大意

给定一个有向图，包含 $n$ 个节点和 $m$ 条有向边。每条边有两种类型：

• 数据边：$w > 0$，表示经过可以获得价值 $w$ 的数据
• 开路边：$w \leq 0$，表示需要花费 $-w$ 来开辟道路

每条边还有限制条件：某些小队不能通过该边。

有 $p$ 个小队从起点 $S$ 出发，终点 $T$ 汇合。要求：

• 每个小队必须找到一条从 $S$ 到 $T$ 的可行路径
• 总收益 = 所有被至少一个小队经过的数据边的价值之和
• 总支出 = 所有被至少一个小队经过的开路边的花费之和
• 目标：最大化 总收益 - 总支出

解题思路

问题分析

这是一个复杂的路径规划与资源分配问题，具有以下特点：

1. 多小队协作：$p$ 个小队独立行动但共享收益
2. 路径限制：每条边有特定的小队通行限制
3. 收益去重：同一条边被多个小队经过只计算一次收益/花费
4. 组合优化：需要同时考虑路径可行性和收益最大化

核心挑战

1. 可行性保证：必须为每个小队找到从 $S$ 到 $T$ 的可行路径
2. 收益优化：在保证可行性的前提下最大化净收益
3. 计算复杂度：图的大小和小队数量可能导致组合爆炸

方法二：优化策略

对于大规模数据，可以采用以下优化策略：

1. 预处理：为每个小队预先计算可通行的边
2. 贪心选择：优先选择高价值的数据边
3. 路径共享：鼓励多个小队使用同一条高价值边
4. 避坑策略：避免使用高花费的开路边

算法分析

时间复杂度

• 基础BFS：$O(p \times (n + m))$，其中 $p$ 是小队数量
• 优化版本：$O(p \times (n + m) \log n)$，使用优先队列

空间复杂度

• $O(n + m)$，存储图结构和路径信息

关键技巧

1. 路径重构：使用parent数组和栈来重构BFS找到的路径
2. 可行性优先：首先保证每个小队都能到达终点，再考虑优化收益
3. 收益估算：在路径搜索时考虑边的价值，引导搜索方向

样例分析

对于题目中的样例：

输入：
4 4 2 1 3
1 3 3
1 2
1 2 5
0
2 3 -2
1 1
3 4 1
0

输出：
2 1 4
3 2 3 4

解释：

• 小队1：路径1→4，收益=3+1=4
• 小队2：路径2→3→4，收益=5+1=6，花费=2
• 总收益=3+5+1=9，总支出=2，净收益=7

总结

本题的关键在于平衡路径可行性和收益最大化两个目标。基础解法保证正确性，优化解法在保证正确性的前提下提升收益。在实际竞赛中，可以根据数据规模选择合适的方法，对于小规模数据可以使用更复杂的优化策略，对于大规模数据则优先保证正确性和运行效率。