🌟 最小费用最大流：让任务分配更聪明

在生活里，常常会遇到“谁去做什么”的问题。比如：

• 班级里要选同学去打扫不同的区域。

• 爸爸妈妈要安排家里的家务。

• 学校里要安排运动会的不同项目。

这些任务，最好安排得既公平又高效。最小费用最大流就是一个能帮忙做“聪明分配”的数学工具。

🎯 问题小故事

想象一下，有 3 个同学：小红、小明、小刚。
有 3 件任务：擦黑板、扫地、倒垃圾。

每个同学做不同的任务，花的“时间”不一样：

目标是：把三件任务分配给三个人，总时间最少。
这就是“任务分配问题”。

🧩 和“最小费用最大流”的关系

• 最大流：表示任务要全部完成（任务都分出去）。

• 最小费用：表示总时间最短（花费最少）。

所以，给每个“同学→任务”的连接线加上“花费”，让算法去找“最省时间的分配方式”。

💡 怎么想象？

把同学看成“水源”，把任务看成“水池”。
水从同学流向任务，每条路有一个“花费”。
算法要让水流完，还要选出花费最小的路线。

这样，结果就是：

• 每个同学分到一个任务。

• 每个任务都有同学完成。

• 总花费最小。

🔑 C++ 示例代码

下面给出一个简单的代码。

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to, cap, cost, rev; // 目标点，容量，费用，反向边编号
};

const int INF = 1e9;
vector<vector<Edge> > graph;
vector<int> dist, prevv, preve;

// 添加一条有向边
void add_edge(int from, int to, int cap, int cost) {
    Edge a = {to, cap, cost, (int)graph[to].size()};
    Edge b = {from, 0, -cost, (int)graph[from].size()};
    graph[from].push_back(a);
    graph[to].push_back(b);
}

// 最小费用流算法
int min_cost_flow(int s, int t, int f) {
    int res = 0;
    while (f > 0) {
        // Dijkstra 找最短路
        dist.assign(graph.size(), INF);
        dist[s] = 0;
        priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
        pq.push(make_pair(0, s));
        while (!pq.empty()) {
            pair<int,int> p = pq.top(); pq.pop();
            int d = p.first, v = p.second;
            if (dist[v] < d) continue;
            for (int i = 0; i < (int)graph[v].size(); i++) {
                Edge &e = graph[v][i];
                if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
                    dist[e.to] = dist[v] + e.cost;
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    pq.push(make_pair(dist[e.to], e.to));
                }
            }
        }
        if (dist[t] == INF) return -1; // 不能再流
        // 找最小流量
        int d = f;
        for (int v = t; v != s; v = prevv[v]) {
            d = min(d, graph[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += d * dist[t];
        for (int v = t; v != s; v = prevv[v]) {
            Edge &e = graph[prevv[v]][preve[v]];
            e.cap -= d;
            graph[v][e.rev].cap += d;
        }
    }
    return res;
}

int main() {
    int n = 3; // 同学数量
    int m = 3; // 任务数量
    int V = n + m + 2; // 点数 = 同学 + 任务 + 源点 + 汇点
    int s = n + m;     // 源点
    int t = n + m + 1; // 汇点
    graph.assign(V, vector<Edge>());
    prevv.assign(V, 0);
    preve.assign(V, 0);

    // 任务耗时表
    int cost[3][3] = {
        {3, 4, 2}, // 小红
        {2, 3, 5}, // 小明
        {4, 2, 3}  // 小刚
    };

    // 源点 → 同学
    for (int i = 0; i < n; i++) add_edge(s, i, 1, 0);
    // 同学 → 任务
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            add_edge(i, n+j, 1, cost[i][j]);
        }
    }
    // 任务 → 汇点
    for (int j = 0; j < m; j++) add_edge(n+j, t, 1, 0);

    // 求最小费用最大流
    int result = min_cost_flow(s, t, n);
    cout << "最小总耗时: " << result << " 分钟" << endl;
}

📖 运行结果

程序会输出：

最小总耗时: 6 分钟

这意味着，按照聪明的分配方式，三件事加起来只要 7 分钟！

🌱 总结

• 最大流 → 确保任务都完成。

• 最小费用 → 找出最省时间的做法。

• 这样的方法，可以用在排班、分配任务、资源分配等很多地方。

看起来是复杂的算法，其实就像“让水走最短路”一样自然。

来仔细分析一下，为什么程序最后输出的结果是 最小总耗时 6 分钟。

🧩 问题回顾

三位同学和三项任务的耗时表如下：

目标是：每人完成一项任务，每项任务恰好分配一个人，总耗时最小。

🔍 穷举几种分配方式

为了更直观，可以尝试列举所有可能分配（3!=6 种情况），看看哪种最省。

方案 A

• 小红 → 擦黑板 (3)

• 小明 → 扫地 (3)

• 小刚 → 倒垃圾 (3)
  总耗时 = 3+3+3 = 9

方案 B

• 小红 → 擦黑板 (3)

• 小明 → 倒垃圾 (5)

• 小刚 → 扫地 (2)
  总耗时 = 3+5+2 = 10

方案 C

• 小红 → 扫地 (4)

• 小明 → 擦黑板 (2)

• 小刚 → 倒垃圾 (3)
  总耗时 = 4+2+3 = 9

方案 D

• 小红 → 扫地 (4)

• 小明 → 倒垃圾 (5)

• 小刚 → 擦黑板 (4)
  总耗时 = 4+5+4 = 13

方案 E

• 小红 → 倒垃圾 (2)

• 小明 → 擦黑板 (2)

• 小刚 → 扫地 (2)
  总耗时 = 2+2+2 = 6 ✅

方案 F

• 小红 → 倒垃圾 (2)

• 小明 → 扫地 (3)

• 小刚 → 擦黑板 (4)
  总耗时 = 2+3+4 = 9

🏆 最优解

从上面 6 种情况对比可见：

• 最小的总耗时是 6 分钟，出现在 方案 E。

• 分配方式为：

• 小红 → 倒垃圾 (2 分钟)

• 小明 → 擦黑板 (2 分钟)

• 小刚 → 扫地 (2 分钟)

每个人都在做自己“最擅长”的事情，总共才花 6 分钟。

🌟 总结

算法最终找到的分配就是 方案 E，因此输出 最小总耗时: 6 分钟。

这种任务分配问题，其实就是“把人分到最合适的工作”，通过 最小费用最大流 或者 匈牙利算法 都能解出来。