题解

算法分析

本题是一个 凸费用流（Convex Cost Flow） 问题，结合了 网络流 和 凸优化 的技巧，使用 分数规划 和 分段积分 的方法求解。

问题本质

我们需要在满足酿酒点产量限制和存酒点容量限制的情况下，最大化总存酒量，并最小化总魔力消耗。魔力消耗函数是二次函数 $a_ix^2 + b_ix$，这是一个凸函数。

核心思路

1. 分数规划：将原问题转化为一系列参数化的最大流问题
2. 凸优化：利用魔力函数的凸性，通过分段线性逼近来求解
3. 网络流建模：将酿酒点和存酒点建模为二分图，使用最大流算法

算法标签

• 凸费用流（Convex Cost Flow）
• 分数规划（Fractional Programming）
• 网络流/最大流（Network Flow / Max Flow）
• 参数化搜索（Parametric Search）
• 凸优化（Convex Optimization）

关键代码解析

// 参数化最大流：对于给定的参数val，计算对应的流量和代价
auto dinic(double val) {
    // 构建网络流图
    for (int i = 1; i <= n; i++)
        if (b[i] < val) {
            if (!a[i])
                add(S, i, c[i]);  // 线性情况
            else
                // 二次函数的最优产量限制
                add(S, i, min(1.0 * c[i], (val - b[i]) / 2 / a[i]));
        }
    
    // 运行Dinic最大流算法
    while (bfs())
        dfs(S, 1e4);
    
    // 计算对应的线性函数系数
    return make_pair(p, q);
}

// 分段求解凸函数
void solve(auto l, auto r) {
    if (l == r) return;
    
    // 计算交点
    dfrac val = (r.second - l.second) / (l.first - r.first);
    auto mid = dinic(val.eval() + eps);
    
    // 递归分段
    solve(l, mid), solve(mid, r);
}

算法步骤

1. 网络流建模：

   • 源点 → 酿酒点：容量受二次函数最优解限制
   • 酿酒点 → 存酒点：根据通道连接
   • 存酒点 → 汇点：容量为存酒点容量

2. 参数化搜索：

   • 对于每个参数 $\lambda$，求解最大流
   • 得到对应的线性函数 $f(\lambda) = p\lambda + q$

3. 凸包构建：

   • 通过递归分段，构建费用函数的凸包
   • 在每个分段上，费用函数是线性的

4. 积分求解：

   • 对凸包分段进行积分，得到总最小费用
   • 输出分数形式的结果

时间复杂度

• Dinic算法：$O(V^2E)$，其中 $V = n + m$，$E \leq 1000$
• 分段次数：由于数据范围小，分段数有限
• 总体复杂度：在数据范围内可接受

空间复杂度

• $O(V + E)$，用于存储网络流图

算法优势

1. 处理凸费用：能够有效处理二次凸费用函数
2. 精确分数输出：直接处理有理数，避免浮点误差
3. 理论保证：基于凸优化理论，保证找到全局最优解

总结

本题通过将凸费用流问题转化为参数化的最大流问题，结合分数规划和分段积分的方法，高效地求解了带有二次费用函数的资源分配问题。这种方法在理论上优雅，在实践中有效，是处理凸费用流问题的经典技术。