最小费用最大流。由于一个工人在给一个顾客服务后还能再给一个顾客服务, 所以把每个顾客和每个工人建点显然不能完成任务。

那么我们考虑把第 $i$ 个工人建成 $n$ 个点,表示为 $P(i,j) (i \in [1, m], j \in [1, n])$。把第 $i$ 个顾客表示为 $T(k)$。

把 $T(k)$ 依次向 $P(i,j)$ 连边,流量为 $1$ ,费用为 $w(k,i) \times j$ 。表示第 $k$ 个顾客被第 $i$ 个工人倒数第 $j$ 个服务对答案产生的贡献(即包括在它之后的人的等待时间,而不是这个人自己的花费)。

最后从源点向每个顾客连流量 $1$ ,费用 $0$ 的边,$n \times m$ 个工人向汇点连流量 $1$ ,费用为 $0$ 的边,跑最小费用最大流即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long
#define rep(i,l,r) for (int i = l; i <= r; i++)
#define getc(x) getchar(x)
#define putc(x) putchar(x)

template <typename T> inline void read(T &x) {
x = 0; register char ch; register bool fl = 0;
while (ch = getc(), ch < 48 || 57 < ch) fl ^= ch == '-'; x = (ch & 15);
while (ch = getc(), 47 < ch && ch < 58) x = (x << 1) + (x << 3) + (ch & 15);
if (fl) x = -x;
}
template <typename T> inline void print(T x, char c = '\n') {
static int buf[40];
if (x == 0) { putc('0'); return; }
if (x < 0) putc('-'), x = -x;
for (buf[0] = 0; x; x /= 10) buf[++buf[0]] = x % 10 + 48;
while (buf[0]) putc((char) buf[buf[0]--]);
putc(c);
}

const int maxn = 4010, maxm = 1000010;

#define at(i,j) ((i) * m + (j))

int n, m, u, v, w, s, e, l, r, ans, flag;
int dis[maxn], pre[maxn], inq[maxn], q[maxn];

int tot = 2, hed[maxn], nxt[maxm], to[maxm], val[maxm], cst[maxm];

inline void add_simple_edge(int u, int v, int w, int c) {
nxt[tot] = hed[u], to[tot] = v, val[tot] = w, cst[tot] = c;
hed[u] = tot++;
}

inline void add_edge(int u, int v, int w, int c) {
add_simple_edge(u, v, w, c);
add_simple_edge(v, u, 0, -c);
}

bool spfa() {
memset(dis, 63, sizeof(dis));
memset(pre, 0, sizeof(pre));
l = r = 1, q[1] = s, inq[s] = 1, dis[s] = 0;
while (l <= r) {
u = q[(l++) % (e + 2)], inq[u] = 0;
for (int i = hed[u], v = to[i]; i; i = nxt[i], v = to[i])
if (val[i] && dis[v] > dis[u] + cst[i]) {
dis[v] = dis[u] + cst[i];
pre[v] = i;
if (!inq[v]) {
inq[v] = 1;
q[(++r) % (e + 2)] = v;
}
}
}
return pre[e];
}

int main() {

read(n), read(m);
s = n * m + m + 1, e = s + 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
read(w);
for (int k = 1; k <= m; k++)
add_edge(i, at(j, k), 1, w * k);
}
}
for (int i = 1; i <= m; i++)
add_edge(s, i, 1, 0);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
add_edge(at(i, j), e, 1, 0);

while (spfa()) {
for (int i = pre[e]; i; i = pre[to[i ^ 1]])
val[i] -= 1, val[i ^ 1] += 1;
for (int i = pre[e]; i; i = pre[to[i ^ 1]])
ans += cst[i];
}
printf("%.2lf\n", ans / (double)m);

return 0;
}