BZOJ 1070: [SCOI2007]修车

太久不写网络流/费用流已经忘得差不多了。
把每个技术人员拆成 \(n\) 个点，表示倒数第 \(i\) 个去修某辆车
那么在它之后修的车就得加上它的时间，所以费用就是 \(i * w\)
所以就是每个顾客 \(x\) 向 \((i, j)\)(第 \(j\) 个技术人员倒数第 \(i\) 个修某辆车) 连一条容量为 \(1\)，费用为 \(i * cost[x][j]\)
源点向 \(x\) 连容量为 \(1\)，费用为 \(0\) 的边
\((i, j)\) 向汇点连容量为 \(1\)，费用为 \(0\) 的边
跑最小费用最大流即可

#include <bits/stdc++.h>

const int INF = 0x3f3f3f3f;
const int N = 5e3;
const int E = N * 67;
int head[N], cnt = 1, to[E], f[E], w[E], ne[E], path[N], dis[N];
bool inq[N];
inline void add(int u, int v, int ff, int c) {
    to[++cnt] = v; f[cnt] = ff; w[cnt] = c; ne[cnt] = head[u]; head[u] = cnt;
    to[++cnt] = u; f[cnt] = 0; w[cnt] = -c; ne[cnt] = head[v]; head[v] = cnt;
}
int m, n;

bool spfa(int s, int t) {
    for (int i = 0; i <= t; i++) dis[i] = INF, path[i] = 0, inq[i] = 0;
    std::queue<int> que;
    que.push(s);
    dis[s] = 0;
    inq[s] = 1;
    while (!que.empty()) {
        int u = que.front(); que.pop();
        inq[u] = 0;
        for (int i = head[u]; i; i = ne[i]) {
            int v = to[i];
            if (f[i] && dis[v] > dis[u] + w[i]) {
                dis[v] = dis[u] + w[i];
                path[v] = i;
                if (!inq[v]) {
                    inq[v] = 1;
                    que.push(v);
                }
            }
        }
    }
    return dis[t] != INF;
}

int mcf(int s, int t) {
    int ans = 0;
    while (spfa(s, t)) {
        int x = INF;
        for (int i = path[t]; i; i = path[to[i ^ 1]]) x = std::min(x, f[i]);
        for (int i = path[t]; i; i = path[to[i ^ 1]]) f[i] -= x, f[i ^ 1] += x;
        ans += x * dis[t];
    }
    return ans;
}   

int main() {
    scanf("%d%d", &m, &n);
    int S = 0, T = n * m + n + 1;
    for (int i = 1; i <= n; i++)
        add(S, i, 1, 0);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int x;
            scanf("%d", &x);
            for (int k = 1; k <= n; k++) {
                add(i, j * n + k, 1, k * x);
            }
        }
    for (int i = n + 1; i < T; i++)
        add(i, T, 1, 0);
    printf("%.2f\n", (double)mcf(S, T) / n);
}

BZOJ 1070: [SCOI2007]修车

原文：https://www.cnblogs.com/Mrzdtz220/p/12323419.html