题解 P2053 【[SCOI2007]修车】

· · 题解

古希腊哲学家赫拉克利曾说：“人不能两次踏进同一条河流。”这句话承认了辩证唯物主义中绝对运动与相对静止的统一的观点，是正确的。

人不能两次踏进同一条河流，因为你第一次踏进的河流和第二次踏进的河流已经不是同一个河流了（水流走了）。同样地，对于一个修车工人而言，修第一辆车的他和修第二辆车的他不是同一个人。

所以本题的错误建图方式是，建一个二分图，左边是车，右边是工人，连边跑最小费用流。这样建图体现的是形而上学的不变论，是错误的。

说人话：对于每个工人而言，他在修第k辆车的时候，之前已经修了k-1辆车，所以对于不同的k，对应的客人等待的时间是不同的，因此我们需要将每个工人拆成n个点，分别表示修第几辆车的他。

但是你会发现这样做的话连边时的边权比较困难。所以我们需要做一个推导。假设某个工人一共修了K辆车，花的时间分别为T_1,T_2,\cdots,T_K，那么当他修第一辆车时，后面的K-1个人必须等着，同时第1个人也要等他修好，所以总共等待时间为K\times T_1；接下来修第二辆车时同理，有K-1个人在等他修，所以时间是(K-1)\times T_2，以此类推，总等待时间即为

\sum\limits_{i=1}^K T_i(K-i+1)

不难发现，他倒数第i个修的车对应的客人总共要贡献T_i\times i的等待时间。于是有了这一步转化，我们可以给出最终的建图方案了：将每个工人拆成n个点，分别表示修倒数第几辆车的他；如果第j个工人修第i辆车要花T(i,j)的时间，我们枚举k=1,\cdots,n，从第i辆车向第j个工人的第k个点连边，容量为1，费用为k\times T(i,j)。然后跑最小费用最大流，最后总费用除以n即可。

#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>

template <typename T> inline void read(T& x) {
    int f = 0, c = getchar(); x = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
    if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
    read(x); read(args...); 
}

const int maxv = 3000, maxe = 1e5, inf = INT_MAX;
int dist[maxv], head[maxv], q[maxv];
bool vis[maxv];
int v[maxe << 1], cap[maxe << 1], cost[maxe << 1], flow[maxe << 1], next[maxe << 1];
int n, m, s, t, V, tot = -1;

inline void ae(int x, int y, int ca, int co) {
    v[++tot] = y; cap[tot] = ca; cost[tot] = co; next[tot] = head[x]; head[x] = tot;
    v[++tot] = x; cap[tot] = 0; cost[tot] = -co; next[tot] = head[y]; head[y] = tot;
}
inline bool bfs() {
    for (int i = 1; i <= V; ++i)
        dist[i] = inf, vis[i] = 0;
    int l = 0, r = 1;
    dist[t] = 0; vis[q[1] = t] = 1;
    while (l < r) {
        int x = q[++l]; vis[x] = 0;
        for (int i = head[x]; ~i; i = next[i])
            if (cap[i ^ 1] > flow[i ^ 1] && dist[v[i]] > dist[x] - cost[i]) {
                dist[v[i]] = dist[x] - cost[i];
                if (!vis[v[i]]) vis[q[++r] = v[i]] = 1;
            }
    }
    return dist[s] < inf;
}
int dfs(int x, int cf, int &mc) {
    vis[x] = 1;
    if (x == t || !cf) return cf;
    int getf = 0;
    for (int i = head[x]; ~i; i = next[i])
        if (!vis[v[i]] && cap[i] > flow[i] && dist[v[i]] == dist[x] - cost[i]) {
            int nf = dfs(v[i], std::min(cf, cap[i] - flow[i]), mc);
            if (nf) {
                flow[i] += nf; flow[i ^ 1] -= nf; getf += nf; cf -= nf;
                mc += nf * cost[i];
                if (!cf) break;
            }
        }
    return getf;
}
inline void mcmf(int &mc, int &mf) {
    mc = mf = 0;
    while (bfs()) {
        vis[t] = 1;
        while (vis[t]) {
            for (int i = 1; i <= V; ++i)
                vis[i] = 0;
            mf += dfs(s, inf, mc);
        }
    }
}

int main() {
    read(m, n);
    s = n + n * m + 1;
    t = V = s + 1;
    for (int i = 1; i <= V; ++i) head[i] = -1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            int x; read(x);
            for (int k = 1; k <= n; ++k)
                ae(i, j * n + k, 1, x * k);
        }
    for (int i = 1; i <= n; ++i) ae(s, i, 1, 0);
    for (int i = 1; i <= n * m; ++i) ae(i + n, t, 1, 0);
    int mc, mf; mcmf(mc, mf);
    printf("%.2lf\n", (double)mc / n);
    return 0;
}

本题有数据加强板：NOI2012的美食节。那道题需要动态加边。不过那题似乎对我这种zkw费用流使用者不太友好，反正我是用EK-spfa过的那题。

最后说一句，如果认为“人甚至一次也不能踏进同一条河流”，那就是相对主义诡辩论，是错误的。