问题理解

我们有：

• 一个 $n$ 个点的 DAG（有向无环图），点 $n$ 是部队起点，点 $1$ 到 $n_1$ 是目标出入口
• 每条边有时间 $t$ 和安全系数 $s$
• 一个二分图结构：$m_1$ 个空腔，每个连接一个奇数编号出入口和一个偶数编号出入口
• 派部队到某个出入口可以探索所有与之相连的空腔
• 单支部队危险性 = 路径总时间 / 路径安全系数和
• 总危险性 = 各部队危险性之和
• 目标：覆盖所有空腔的前提下最小化总危险性

---

关键观察

1. 问题结构分析

• 空腔形成二分图：左部是奇数出入口，右部是偶数出入口
• 覆盖空腔 = 选择一些出入口，使得每条边（空腔）至少有一个端点被选中
• 这是典型的二分图点覆盖问题

2. 危险性计算的特殊性

危险性定义： [ \text{危险性} = \frac{\text{总时间}}{\text{安全系数和}} = \frac{\sum t_i}{\sum s_i} ] 这是一个分式线性函数，需要用到分数规划技巧。

3. 部队派遣独立性

每个出入口可以独立派遣部队，且部队从同一起点 $n$ 出发。

---

算法框架

步骤1：分数规划转化

设 $x_i$ 表示是否派遣部队到出入口 $i$，$c_i$ 是到出入口 $i$ 的最小危险性。

原问题： [ \min \sum_{i=1}^{n_1} c_i x_i \quad \text{s.t. } x \text{ 是二分图点覆盖} ]

但 $c_i$ 本身也是分式：$c_i = \frac{T_i}{S_i}$，其中 $T_i$ 是到 $i$ 的最短时间，$S_i$ 是最大安全系数和。

分数规划思路：二分答案 $λ$，判断是否存在方案使得： [ \sum \frac{T_i}{S_i} x_i \leq λ ] 等价于： [ \sum (T_i - λ S_i) x_i \leq 0 ]

步骤2：计算单点代价

对每个出入口 $i$，我们需要找到从 $n$ 到 $i$ 的路径，最小化 $T - λS$。

由于图是 DAG，可以用 DP 或 BFS 计算：

• 状态：$dp[u]$ 表示从 $n$ 到 $u$ 的最小 $T - λS$
• 转移：$dp[v] = \min(dp[v], dp[u] + t - λs)$

对每个 $λ$，预处理所有 $dp[i]$（$1 \leq i \leq n_1$）。

步骤3：二分图点覆盖

现在问题转化为：选择一些出入口，覆盖所有空腔，且 $\sum w_i x_i \leq 0$，其中 $w_i = dp[i]$。

网络流建模：

• 源点 $S$ 连所有奇数出入口，容量 $w_i$（若 $w_i > 0$）或 $∞$（若 $w_i \leq 0$）
• 所有偶数出入口连汇点 $T$，容量 $w_i$（若 $w_i > 0$）或 $∞$（若 $w_i \leq 0$）
• 每个空腔 $(u,v)$：$u$（奇数）向 $v$（偶数）连容量 $∞$ 的边

最小割定理：该网络的最小割对应最小点权和覆盖。

步骤4：二分判断

对给定的 $λ$：

• 计算所有 $w_i = dp[i]$
• 建网络流图，求最小割
• 如果最小割值 $\leq 0$，则 $λ$ 可行，否则不可行

二分 $λ$ 直到精度足够。

---

算法流程

1. 分数规划：二分危险性 $λ$
2. 单源最短路：在 DAG 上 DP 计算每个出入口的 $T - λS$
3. 网络流判定：建图求最小割，判断 $λ$ 是否可行
4. 输出：找到最小的可行 $λ$，保留一位小数

---

复杂度分析

• 二分次数：$O(\log(\frac{\text{范围}}{\text{精度}}))$，约 $O(\log(10^5)) \approx 20$
• DP 计算：每次 $O(n + m)$，$n \leq 700, m \leq 10^5$，可行
• 网络流：二分图，$n_1 \leq 160$，使用 Dinic 复杂度 $O(n_1^2 \cdot m_1)$，$m_1 \leq 40000$，可行

---

样例分析

样例中：

• $n=5, m=5$，起点是 5
• 4 个空腔：$(1,2), (1,4), (3,2), (3,4)$
• 需要覆盖所有空腔，最优方案是选择出入口 1 和 2
• 计算得到最小危险性 17.0

---

特殊情况处理

• 无解情况：如果存在空腔无法被任何部队覆盖（即两个端点都不可达），输出 -1
• 精度处理：保留一位小数，注意四舍五入
• 无穷大处理：不可达的出入口代价设为 $∞$

---

总结

这道题的核心是：

1. 分数规划：将分式目标转化为线性判定问题
2. DAG 上 DP：高效计算单点代价
3. 网络流建模：将点覆盖问题转化为最小割
4. 二分答案：在实数域上寻找最优解

通过将原问题分解为这几个子问题，可以高效求解这个复杂的优化问题。