题解 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$即可。 ```cpp #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过的那题。 最后说一句，如果认为“人甚至一次也不能踏进同一条河流”，那就是相对主义诡辩论，是错误的。