Minimum-costFlow - 题解

标签与难度

标签: 最小费用最大流, 网络流, SPFA, 凸性, 前缀和, 图论难度: 2200

题目大意喵~

你好呀，指挥官！这道题是说，我们有一个由 $N$ 个节点和 $M$ 条有向边组成的网络，喵~ 每条边从一个节点指向另一个节点，并且通过它需要花费一定的成本 $c$ 。

然后呢，会有 $Q$ 次询问。每次询问会给我们两个数字 $u$ 和 $v$ 。这其实是在问：如果我们要从源点（节点1）向汇点（节点 $N$ ）输送总量为 $F = v/u$ 个单位的流量，那么平均每个单位流量的最小成本是多少呢？

如果根本无法输送那么多流量（比如网络的最大流量都小于 $v/u$ ），就要告诉人家 "NaN" 哦。最后的结果要以最简分数的形式输出，呐。

解题思路分析

这道题表面上看起来是经典的最小费用流问题，但加上了分数流量和多组询问，就变得有趣起来了呢，喵~！直接对每次询问都跑一次带分数的网络流算法，肯定会超时的说。所以我们需要找到更聪明的办法！

流量与成本的凸关系

首先，我们来思考一下输送流量和成本之间的关系。在最小费用流中，我们总是优先走“最便宜”的路。

第一滴水：当我们输送第一个单位的流量时，算法会找到一条从源点到汇点成本最低的路径（也就是最短路）。这条路径的成本，就是输送第一个单位流量的边际成本，我们叫它 $c_1$ 吧。
第二滴水：当我们想再多送一个单位的流量时，原来的那条路可能因为容量限制（题目中每条边的容量可以看作1）不能再满负荷走了，或者走了之后反向边的出现使得网络中出现了新的、可能更优的路径。算法会再次找到当前残留网络中的一条最短路，它的成本是 $c_2$ 。根据贪心策略，一定有 $c_1 \le c_2$ 。
依此类推：我们每多输送一个单位的流量，它的边际成本 $c_i$ 都是当前网络状态下的最短路长度。这个成本序列 $c_1, c_2, c_3, \dots$ 是非递减的。

所以，总成本 $C(f)$ 作为总流量 $f$ 的函数，是一个凸函数！它的斜率（也就是边际成本）是分段的常数，并且是递增的。就像这样：

C(f) = \sum_{i=1}^{\lfloor f \rfloor} c_i + (f - \lfloor f \rfloor) \cdot c_{\lfloor f \rfloor + 1}

这里 $\lfloor f \rfloor$ 是 $f$ 的整数部分。这个公式的意思是：要输送 $f$ 的流量，我们先把整数部分 $\lfloor f \rfloor$ 的流量以 $c_1, c_2, \dots, c_{\lfloor f \rfloor}$ 的成本一个个送完，总成本是 $\sum_{i=1}^{\lfloor f \rfloor} c_i$ 。剩下的小数部分 $(f - \lfloor f \rfloor)$ 就按下一个单位的成本 $c_{\lfloor f \rfloor + 1}$ 来计算。

算法核心思路

既然询问很多，而图是固定的，我们可以先把所有的边际成本 $c_1, c_2, \dots, c_{\text{max\_flow}}$ 都预处理出来！

预处理边际成本: 我们可以用经典的基于SPFA的连续最短路算法来求解最小费用最大流。我们建立一个流量网络，源点是1，汇点是 $N$ 。对于原图中的每条边 u -> v，成本为 cost，我们在流量网络中添加一条容量为1，费用为 cost 的边。然后，我们循环执行以下操作：
- 用SPFA在残留网络中找到一条从源点到汇点的费用最小的路径（即最短路）。
- 如果找不到路径了，说明已经达到最大流，预处理结束。
- 如果找到了，路径的长度就是下一个单位流量的边际成本。我们把它记录到一个列表 path_costs 里。
- 然后我们沿着这条路径增广1个单位的流量（更新残留网络）。
这个过程结束后，path_costs 列表里就按顺序存储了 $c_1, c_2, \dots, c_{\text{max\_flow}}$ 。
处理询问: 对于每个询问 $(u, v)$ ，我们要计算输送 $F = v/u$ 流量的平均成本，也就是 $C(F) / F$ 。
- 首先，检查可行性。如果 $v/u$ 大于我们的最大流量（即 path_costs.size()），那肯定是送不到的，输出 "NaN"。
- 令 $k = \lfloor F \rfloor = v / u$ （整数除法），以及 $rem = v \pmod u$ 。
- 那么总流量 $F = k + rem/u$ 。
- 根据我们上面的凸函数公式，总成本 $C(F)$ 为：
$C(F) = \left( \sum_{i=1}^{k} c_i \right) + \frac{rem}{u} \cdot c_{k+1}$
- 要求的平均成本就是 $C(F) / F = C(F) / (v/u)$ 。为了避免浮点数计算带来的精度问题，我们把它表示成分数形式：
$\text{平均成本} = \frac{C(F) \cdot u}{v} = \frac{\left( \left( \sum_{i=1}^{k} c_i \right) + \frac{rem}{u} \cdot c_{k+1} \right) \cdot u}{v} = \frac{\left( \sum_{i=1}^{k} c_i \right) \cdot u + rem \cdot c_{k+1}}{v}$
- 为了快速计算 $\sum c_i$ ，我们可以预处理 path_costs 的前缀和。
- 这样，分子 numerator = prefix_sum_costs[k] * u + rem * c_{k+1}，分母 denominator = v。
- 最后，用 gcd 化简这个分数再输出就好啦，喵~

这样，我们就把问题转化成了“一次MCMF预处理 + 多次 $O(1)$ 查询”，完美解决了！

代码实现

这是我根据上面的思路，精心重构的一份代码哦！希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <numeric> // For std::gcd

// 使用 long long 防止费用累加时溢出
using int64 = long long;

const int64 INF = 1e18; // 使用一个足够大的数表示无穷大
const int MAXN = 55;   // 最大节点数

// 边的结构体
struct Edge {
    int to;       // 这条边指向的节点
    int capacity; // 剩余容量
    int64 cost;   // 费用
    int rev;      // 反向边的索引
};

// 全局变量区
int N, M; // 节点数和边数
std::vector<Edge> adj[MAXN]; // 邻接表存图
int64 dist[MAXN]; // SPFA用的距离数组
int parent_v[MAXN], parent_e[MAXN]; // 记录增广路径
bool in_queue[MAXN]; // SPFA用的标记数组

// 添加一条从 u 到 v，容量为 cap，费用为 cost 的边
void add_edge(int u, int v, int cap, int64 cost) {
    adj[u].push_back({v, cap, cost, (int)adj[v].size()});
    adj[v].push_back({u, 0, -cost, (int)adj[u].size() - 1}); // 反向边
}

// SPFA 寻找费用最小的增广路
bool spfa(int s, int t) {
    // 初始化
    for (int i = 1; i <= N; ++i) {
        dist[i] = INF;
        in_queue[i] = false;
    }
    dist[s] = 0;
    
    std::queue<int> q;
    q.push(s);
    in_queue[s] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;

        for (size_t i = 0; i < adj[u].size(); ++i) {
            Edge &e = adj[u][i];
            if (e.capacity > 0 && dist[e.to] > dist[u] + e.cost) {
                dist[e.to] = dist[u] + e.cost;
                parent_v[e.to] = u;
                parent_e[e.to] = i;
                if (!in_queue[e.to]) {
                    q.push(e.to);
                    in_queue[e.to] = true;
                }
            }
        }
    }
    return dist[t] != INF;
}

int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    while (std::cin >> N >> M) {
        // --- 初始化 ---
        for (int i = 1; i <= N; ++i) {
            adj[i].clear();
        }

        for (int i = 0; i < M; ++i) {
            int u, v;
            int64 c;
            std::cin >> u >> v >> c;
            add_edge(u, v, 1, c);
        }

        int source = 1, sink = N;
        std::vector<int64> path_costs;

        // --- 预处理：用MCMF找出所有边际成本 ---
        while (spfa(source, sink)) {
            path_costs.push_back(dist[sink]);
            
            // 沿着找到的路径增广流量
            int u = sink;
            while (u != source) {
                int prev_u = parent_v[u];
                int edge_idx = parent_e[u];
                adj[prev_u][edge_idx].capacity -= 1;
                int rev_edge_idx = adj[prev_u][edge_idx].rev;
                adj[u][rev_edge_idx].capacity += 1;
                u = prev_u;
            }
        }
        
        // --- 预处理：计算边际成本的前缀和 ---
        int max_flow = path_costs.size();
        std::vector<int64> prefix_sum_costs(max_flow + 1, 0);
        for (int i = 0; i < max_flow; ++i) {
            prefix_sum_costs[i + 1] = prefix_sum_costs[i] + path_costs[i];
        }

        // --- 处理询问 ---
        int Q;
        std::cin >> Q;
        while (Q--) {
            int64 u_query, v_query;
            std::cin >> u_query >> v_query;

            // 检查流量是否可行
            if (v_query > u_query * max_flow) {
                std::cout << "NaN\n";
                continue;
            }
            
            if (v_query == 0) {
                 std::cout << "0/1\n";
                 continue;
            }

            int64 k = v_query / u_query;
            int64 rem = v_query % u_query;

            int64 numerator = 0;
            if (k > 0) {
                numerator += prefix_sum_costs[k] * u_query;
            }
            if (rem > 0) {
                // path_costs[k] 是第 k+1 条路径的成本 (0-indexed)
                numerator += path_costs[k] * rem;
            }
            
            int64 denominator = v_query;
            
            // 化简分数
            int64 common_divisor = std::gcd(numerator, denominator);
            std::cout << numerator / common_divisor << "/" << denominator / common_divisor << "\n";
        }
    }

    return 0;
}

复杂度分析

时间复杂度: $O(F \cdot \text{SPFA} + Q)$ ，其中 $F$ 是最大流。
- SPFA在最坏情况下是 $O(N \cdot M)$ 。
- 最大流 $F$ 的上限是 $M$ （因为每条原始边的容量都是1）。
- 所以预处理部分的复杂度是 $O(M \cdot N \cdot M) = O(N \cdot M^2)$ 。
- 查询部分，由于我们预计算了前缀和，每次查询都是 $O(1)$ 的。总查询时间是 $O(Q)$ 。
- 总时间复杂度为 $O(N \cdot M^2 + Q)$ 。对于本题的数据范围 ( $N \le 50, M \le 100$ )，这是完全可以接受的！
空间复杂度: $O(N + M)$ 。
- 邻接表存储图需要 $O(N+M)$ 的空间。
- SPFA算法需要 $O(N)$ 的辅助空间。
- path_costs 和 prefix_sum_costs 列表最多存储 $M$ 个元素，需要 $O(M)$ 的空间。
- 所以总空间复杂度是 $O(N+M)$ ，非常节省空间的说！

知识点总结

这道题真是一次愉快的思维探险呢，喵~！我们从中可以学到：

最小费用流的凸性: 核心思想是理解最小费用流的总费用函数 $C(f)$ 是关于流量 $f$ 的一个下凸函数。它的导数（边际成本）是分段递增的。
MCMF求边际成本: 经典的基于SPFA的连续最短路算法，不仅能求出最小费用，其每一次找到的增广路成本，恰好就是按顺序排列的边际成本。
预处理与查询分离: 当图固定而查询很多时，应该思考是否可以对图的某些性质进行预处理，从而加速查询。这里我们预处理了所有边际成本和它们的前缀和。
分数处理: 面对分数计算，尽量全程使用整数运算，通过通分等方式避免浮点数精度误差。这里的平均成本公式推导就是一个很好的例子。
算法模板: 这是一个很好的练习最小费用最大流（MCMF）算法模板的机会，特别是SPFA在带负权（反向边）的图上寻找最短路的应用。

希望这篇题解能让你对网络流有更深的理解！一起加油，成为更厉害的算法大师吧，喵~！

Minimum-costFlow - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

流量与成本的凸关系 ​

算法核心思路 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​