P2053 [SCOI2007] 修车
大意
\(N\) 个顾客，\(M\) 个技术人员，不同的技术人员对不同的车的修理时间是不同的，那么求顾客们的最短等待时间。
思路
我们发现，对于这个题来说，很像排队接水(不是)。
考虑每个技术人员的时候，我们发现如下规律，一个技术人员对答案所作出的贡献是：
\[最后一个顾客时间 \times 1 + 倒数第二个顾客时间 \times 2 ... 倒数第 k 个顾客时间 \times k
\]
我们发现，每个技术人员在不同时刻的状态是不一样的，对答案所做出的贡献也是，不一样的，但是每个状态下的技术人员只能给一个人修车，但是顾客可以自行选择某个状态下的某个技术人员。
这个问题我们可以用网络流来解决，我们对于每个技术人员，将其拆分为 \(n\) 个状态，对于正在给倒数第 \(k\) 个顾客修车的师傅 \(i\) 对顾客 \(j\) 连一条容量为 \(1\)，费用为 \(t_{i, j} \times k\)，对于源点向每个技术人员的每个状态连容量为 \(1\)，花费为 \(0\) 的边，对于每个顾客都向汇点 \(T\) 去连上容量为 \(1\)，花费为 \(0\) 的边。
这样跑出的最小费用最大流就一定会自己最优的选择出最短的排队修车的时间。
代码
#include<bits/stdc++.h>
using namespace std;const int MAXN = 1005;
const int MAXM = 100005;
struct node{int u, v, nxt, c, w;
}e[MAXM * 2];int S, T;
int tot, h[MAXN], d[MAXN], pre[MAXN];
bool vis[MAXN];void init(){tot = 0;memset(h, -1, sizeof(h));
}void add(int u, int v, int c, int w){e[tot] = {u, v, h[u], c, w};h[u] = tot ++;e[tot] = {v, u, h[v], 0, -w};h[v] = tot ++;
}bool spfa(){memset(vis, 0, sizeof(vis));memset(d, 0x3f, sizeof(d));memset(pre, -1, sizeof(pre));queue<int> q;q.push(S);d[S] = 0;vis[S] = true;while(!q.empty()){int u = q.front();q.pop();vis[u] = false;for(int i = h[u];~i;i = e[i].nxt){int v = e[i].v;if(e[i].c > 0){if(d[v] > d[u] + e[i].w){d[v] = d[u] + e[i].w;pre[v] = i;if(!vis[v]){q.push(v);vis[v] = true;}}}}}return (d[T] != 0x3f3f3f3f);
}int EK(){int res = 0;while(spfa()){int Min = 1e9;for(int i = T;i != S;i = e[pre[i]].u){Min = min(Min, e[pre[i]].c);}for(int i = T;i != S;i = e[pre[i]].u){e[pre[i]].c -= Min;e[pre[i] ^ 1].c += Min;res += e[pre[i]].w * Min;}}return res;
}int m, n;int main(){// freopen("repair.in", "r", stdin);// freopen("repair.out", "w", stdout);cin >> m >> n;init();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 t_cost;cin >> t_cost;for(int k = 1;k <= n;k ++){int pos = n + (j - 1) * n + k;add(i, pos, 1, k * t_cost);}}}for(int j = 1;j <= m;j ++){for(int k = 1;k <= n;k ++){add(n + (j - 1) * n + k, T, 1, 0);}}int ans = EK();printf("%.2f\n", (double)ans / n);return 0;
}