题意理解

我们有一个机器，包含 $n$ 个节点，每个节点有电势 $h_i$。机器内部有 $m$ 条单向运输管道。每个节点有入口管道和出口管道，入口管道有能量损耗 $a_{i,j}$，出口管道有能量损耗 $b_{i,j}$。

一个电荷从节点 $x$ 的第 $i$ 个入口进入，从节点 $y$ 的第 $j$ 个出口离开，获得的能量为：

$$E = h_x - h_y - a_{x,i} - b_{y,j}$$

目标是选择一组电荷路径，最大化总能量。

核心思路

关键观察 1：网络流建模

这是一个典型的分配问题，可以转化为最大费用最大流：

• 源点连接到所有入口管道
• 入口管道连接到对应的机器节点
• 机器节点之间通过内部管道连接
• 机器节点连接到对应的出口管道
• 出口管道连接到汇点

关键观察 2：费用设置

每条边的费用设置为对应的能量值：

• 源点到入口：费用 = $h_x - a_{x,i}$
• 机器节点间：费用 = $0$（内部运输不耗能）
• 出口到汇点：费用 = $-h_y - b_{y,j}$

总费用就是总能量。

关键观察 3：整体二分优化

由于数据规模可能很大，直接运行费用流可能超时。可以使用整体二分来优化：

• 二分可能的流量值
• 在每层递归中，只考虑费用较高的边
• 通过分治减少每次运行流网络的规模

算法框架

方法一：直接费用流

建图步骤：

1. 创建源点 $S$ 和汇点 $T$
2. 为每个入口管道创建节点，$S$ 到入口容量1，费用 $h_x - a_{x,i}$
3. 入口连接到对应机器节点，容量1，费用0
4. 机器节点间按题目给的边连接，容量∞，费用0
5. 机器节点连接到对应出口管道，容量1，费用0
6. 出口管道连接到 $T$，容量1，费用 $-h_y - b_{y,j}$

算法选择：使用zkw费用流或Primal-Dual算法。

方法二：整体二分优化

分治框架：

1. 将所有边按费用从大到小排序
2. 在区间 $[l, r]$ 上：
   • 取中点 $mid$
   • 只保留费用 $\geq mid$ 的边建图
   • 运行最大流，得到当前区间的解
   • 递归处理左右子区间

优势：每次建图规模较小，总体复杂度更优。

方法三：贪心匹配

对于特殊性质（如树结构、链结构），可以使用更高效的贪心算法：

• 按费用从高到低排序边
• 依次尝试匹配，使用并查集维护连通性
• 时间复杂度 $O(m \log m)$

复杂度分析

直接费用流

• 节点数：$O(\sum p_i + \sum q_i + n)$
• 边数：$O(\sum p_i + \sum q_i + m)$
• 复杂度：$O(\text{网络流复杂度})$，可能达到 $O(nm)$

整体二分优化

• 递归层数：$O(\log W)$，$W$ 是费用范围
• 每层流量：$O(\min(\sum p_i, \sum q_i))$
• 总复杂度：$O(\log W \cdot \text{网络流复杂度})$

实现细节

费用流算法选择

zkw费用流：

• 基于SPFA的最短路
• 适合稀疏图
• 在随机数据下表现良好

Primal-Dual：

• 基于Dijkstra的最短路
• 需要势函数处理负权边
• 理论复杂度更优

图建模优化

1. 节点合并：相同费用的管道可以合并
2. 边压缩：多重边合并为一条边，容量叠加
3. 提前终止：当无法找到增广路时提前结束

数值处理

由于涉及大整数运算：

• 使用long long存储中间结果
• 注意数值溢出问题
• 最终结果取模（如果需要）

特殊情况处理

性质A：相邻节点连接

• 图呈链状或环状
• 可以使用动态规划优化

性质B：树结构

• $m = n-1$ 且形成树
• 可以使用树形DP或贪心

性质C：大规模稀疏图

• $n$ 较大但度数有限
• 适合使用zkw费用流

总结

本题的核心在于：

1. 问题识别：认识到这是最大费用最大流问题
2. 图建模：正确建立网络流模型
3. 算法选择：根据数据规模选择合适的流算法
4. 优化技巧：使用整体二分处理大规模实例

这是一个典型的网络流应用题目，考察选手将实际问题转化为经典算法问题的能力，以及在大规模数据下的优化技巧，符合集训队互测的高标准要求。