[SCOI2007] 修车

题目解析

直觉: 二分图

尝试DP想法: 前i个人处理j个车,dp[i][j] , 还要考虑第i个人修车的顺序,还要考虑到每个每个车对每个人每个位置都不一样,那需要具体考虑到车这个集合的不同的车,(状态压缩), 这个复杂度应该很高 ,至少 $2^{60}$

设第 $j$ 位技术人员依次维修了 $k$ 辆车，耗时分别为 $w_1, w_2, \dots, w_k$ 。

第 1 辆车的车主等待时间为： $w_1$
第 2 辆车的车主等待时间为： $w_1 + w_2$
第 $k$ 辆车的车主等待时间为： $w_1 + w_2 + \dots + w_k$

总等待时间（即所有车主等待时间之和）为：

\sum_{i=1}^k (w_1 + \dots + w_i) = k \cdot w_1 + (k-1) \cdot w_2 + \dots + 1 \cdot w_k

数学结构： 这是一个典型的线性加权和。我们可以观察到一个“指纹特征”：第 $j$ 位技术人员维修的倒数第 $p$ 辆车，会对总等待时间产生 $p \times T_{i,j}$ 的贡献。

感觉: 是一个N x N 的格子, 然后 1. 每个格子可以看放一个物品, 2. 每个物品的价值不一样 3. 可以放N个物品, 4. 求最大的价值, 5 利用费用流的功能: 固定流量的最小费用
确实是二分图,每个车只有两个状态, 选和,被选, 且被选态是互斥的.

这道题目是**费用流（Minimum Cost Maximum Flow）**在任务调度问题中的经典应用。由于 $M$ 和 $N$ 的规模较小（ $M \le 9, N \le 60$ ），我们可以通过拆点构建二分图，将“等待时间”转化为“流量消耗”。

你的直觉非常敏锐！你刚才描述的这个模型在离散数学和运筹学中被称为二分图最优匹配（Optimal Bipartite Matching），而用网络流的语言表达，它确实就是**“固定流量为 $N$ 时的最小/最大费用流”**。

我们可以把你的“修车问题”和你描述的“ $N \times N$ 格子模型”做个精准的映射：

1. 模型对齐：从修车到格子

修车问题元素	N×N 格子模型元素	意义
车 (Customer)	横坐标 (Row)	必须被满足的 $N$ 个需求。
维修位 (Tech $\times$ Pos)	纵坐标 (Column)	可供选择的 $N \times M$ 个槽位。
等待时间贡献 ( $p \cdot T_{i,j}$ )	格子里的价值 (Value)	选定某个格子（任务分配）的代价。
每辆车修一次	每行只能选一个	流量平衡限制。
每个位置修一辆车	每列只能选一个	资源排他性限制。

2. 费用流的核心功能：固定流量

正如你所说，费用流在这里起到了**“在保证业务完成（流量=N）的前提下，寻找最优解”**的作用：

流量 (Flow) = N：这是一种“硬约束”，确保了 $N$ 辆车都被处理了。在 $N \times N$ 格子里，这代表我们必须填满 $N$ 个格子。
最小费用 (Min Cost)：在所有能达到流量 $N$ 的路径组合中，算法通过 SPFA/Dijkstra 不断寻找当前的“最短路”（代价最小的路径），从而实现全局最优。

3. 逻辑驱动：离散数学视角下的“独立集”

如果你从离散数学的角度看，这其实是在一个加权大二分图中寻找一个大小为 $N$ 的匹配。

算子映射：题目中的“维修顺序”是一个排列算子，通过拆点，我们将这个排列算子降维映射到了二维平面的布尔矩阵（即你的 $N \times N$ 格子）。
思维模版：
- 输入：一个需求集 $A$ ，一个资源集 $B$ ，以及 $A \times B$ 的代价矩阵。
- 约束： $A$ 中每个元素必选， $B$ 中每个元素最多选一次。
- 目标： $\min \sum \text{Cost}(a, b)$ 。
- 解法：建立 $S \to A$ (cap:1, cost:0)， $B \to T$ (cap:1, cost:0)， $A \to B$ (cap:1, cost:weight)。

4. 错题强化：为什么不能直接 $N \times M$ ？

你可能会疑惑：为什么要拆成 $N \times (N \times M)$ ，而不是直接 $N$ 个车对应 $M$ 个修理工？

思维盲点：如果只对应 $M$ 个工人，你无法在建模中体现“先后顺序”产生的不同权重。

直接连边，费用只能是 $T_{i,j}$ 。
拆点后，费用变成了 $1 \cdot T_{i,j}, 2 \cdot T_{i,j}, \dots, p \cdot T_{i,j}$ 。
本质：你把“时间”这个连续变量，通过“倒数第几个”这个离散索引，转化成了空间上的不同节点。

🛠️ 网络流建模

节点设计

源点 $S$ ，汇点 $T$ 。
车辆节点： $V_1, V_2, \dots, V_N$ 。
技术人员拆点：每个技术人员 $j$ 拆成 $N$ 个位置 $P_{j,1}, P_{j,2}, \dots, P_{j,N}$ 。

连边逻辑

$S \to V_i$ ：容量 $1$ ，费用 $0$ 。（每辆车必须被修一次）
$P_{j,p} \to T$ ：容量 $1$ ，费用 $0$ 。（每个维修位置只能修一辆车）
$V_i \to P_{j,p}$ ：容量 $1$ ，费用 $p \cdot T_{i,j}$ 。（第 $i$ 辆车交给第 $j$ 个人倒数第 $p$ 个修）。

总点数： $N + NM + 2 \approx 60 + 540 = 600$

总边数： $N + NM + N^2M \approx 60 + 540 + 32400 \approx 3.3 \times 10^4$

这个规模在 Dinic 或 SPFA-MCMF 的承受范围内。

📶 信号反射 & 思维模板

关键信号 (Key Signals)：
- 出现 “分配问题 (Assignment Problem)”。
- 出现 “每个位置/顺序的代价权重不同”。
逻辑跃迁 (Logic Jump)：

看到“顺序影响代价”，立刻跳过动态规划的纠结，直接进行**“维度展开”**——将“顺序”这一维度拆解为并列的虚拟节点，化动态分配为静态匹配。
模式识别 (Pattern Recognition)：

以后看到 “任务 A 分配给资源 B，且代价取决于它是 B 处理的第几个”，本能反应就应该是 “权重拆点 + 固定流量费用流”。

代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * 题目：P2053 [SCOI2007] 修车
 * 思路：费用流。将每个技术人员拆分为 N 个节点，表示该技术人员倒数第 p 次修理。
 * 若某辆车是该工人的倒数第 p 个修理的，那么它及其后面修理的共 p 个人都要等待这段时间。
 * 故产生的贡献（费用）为 p * T_{i,j}。
 */

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

// 节点数最大值：源点+汇点+车(60)+工人拆点(9*60) = 602
const int maxn = 1000; 
// 边数最大值：S->车(60) + 拆点->T(540) + 车->拆点(60*540) = 33000。注意反向边翻倍
const int maxe = 100000; 
const int INF_INT = 0x3f3f3f3f;

struct linkList {
    struct edge {int u,v,w,c,next;};
    edge e[maxe];
    int h[maxn], edge_cnt = 0;
    linkList() { reset(); }
    void reset() {
        edge_cnt = 0;
        memset(h, -1, sizeof(h));
    }
    void add(int u, int v, int w = 0, int c = 0) {
        e[edge_cnt] = {u, v, w, c, h[u]};
        h[u] = edge_cnt++;
    }
    edge& operator[](int i) { return e[i]; }
} e;

struct MCMF {
    int dis[maxn], flow[maxn], pre[maxn], last[maxn];
    bool vis[maxn];
    int n;
    long long max_flow, min_cost;

    void init(int n) {
        e.reset();
        this->n = n;
    }

    void addEdge(int u, int v, int cap, int cost) {
        e.add(u, v, cap, cost);
        e.add(v, u, 0, -cost);
    }

    bool spfa(int s, int t) {
        for(int i = 0; i <= n; i++) dis[i] = INF_INT, vis[i] = 0, flow[i] = INF_INT;
        queue<int> q;
        dis[s] = 0; vis[s] = 1; pre[t] = -1;
        q.push(s);

        while (!q.empty()) {
            int u = q.front(); q.pop();
            vis[u] = 0;
            for(int i = e.h[u]; ~i; i = e[i].next) {
                int v = e[i].v, cap = e[i].w, cost = e[i].c;
                if (cap > 0 && dis[v] > dis[u] + cost) {
                    dis[v] = dis[u] + cost;
                    pre[v] = u;
                    last[v] = i;
                    flow[v] = min(flow[u], cap);
                    if (!vis[v]) { vis[v] = 1; q.push(v); }
                }
            }
        }
        return pre[t] != -1;
    }

    void solve(int s, int t) {
        max_flow = 0; min_cost = 0;
        while (spfa(s, t)) {
            int now = t, f = flow[t];
            max_flow += f;
            min_cost += (long long)f * dis[t];
            while (now != s) {
                int idx = last[now];
                e[idx].w -= f;
                e[idx ^ 1].w += f;
                now = pre[now];
            }
        }
    }
} mcmf;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int M, N; // M 技术人员, N 顾客
    if (!(cin >> M >> N)) return 0;

    int S = 0, T = N + M * N + 1;
    mcmf.init(T);

    // 1. 源点向每辆车连边，流量1，费用0
    for (int i = 1; i <= N; ++i) {
        mcmf.addEdge(S, i, 1, 0);
    }

    // 2. 读取修理时间，并向技术人员的每个“倒数位置”连边
    for (int i = 1; i <= N; ++i) { // 第 i 辆车
        for (int j = 1; j <= M; ++j) { // 第 j 位技术人员
            int time; cin >> time;
            for (int p = 1; p <= N; ++p) { // 该工人的倒数第 p 个修理位
                // 费用计算：倒数第 p 个修，会贡献 p 次该车的修理时间
                int tech_pos_node = N + (j - 1) * N + p;
                mcmf.addEdge(i, tech_pos_node, 1, p * time);
            }
        }
    }

    // 3. 每个技术人员的每个修理位向汇点连边，流量1，费用0
    for (int j = 1; j <= M; ++j) {
        for (int p = 1; p <= N; ++p) {
            int tech_pos_node = N + (j - 1) * N + p;
            mcmf.addEdge(tech_pos_node, T, 1, 0);
        }
    }

    mcmf.solve(S, T);

    // 平均等待时间 = 总等待时间 / N
    cout << fixed << setprecision(2) << (double)mcmf.min_cost / N << endl;

    return 0;
}

目录