目录

• 题目
• 解法
• 代码

题目

传送门

解法

首先平均等待时间最小就是总等待时间最小。

对于一位师傅，如果他修了 \(s\) 辆车，第 \(i\) 个被修的车为 \(p_i\)，修车时间为 \(t_i\)。那么第 \(i\) 辆车的等待时间为第 \(i\) 辆车的等待时间 \(+t_i\)。那么 \(s\) 辆车的总时间就是 \(\sum_{i=1}^s t_i\times (s-i+1)\)。

但这样还是不好做，因为 \(t_i\) 的系数和 \(s\) 挂钩。

我们可以修改一下定义：设倒数第 \(i\) 个被修的车为 \(p_i\)，修车时间为 \(t_i\)。那么 \(s\) 辆车的总时间就是 \(\sum_{i=1}^s t_i\times i\)。

接下来考虑如何建图。

1. 首先对于每辆车，由于只能被修一次，从 \(S\) 连一条容量为 \(1\)，边权为 \(0\) 的边。
2. 每个师傅 \(j\) 拆成 \(n\) 个点（拆的点向 \(T\) 连一条容量为 \(1\)，边权为 \(0\) 的边），表示修第 \(i\) 辆车，枚举修的第 \(i\) 辆车 \(k\)，则 \(k\) 向点连容量为 \(1\)，边权为 \(T_{k,j}\times i\) 的边。

跑最小费用最大流即可。

考虑正确性。最大流肯定能保证 \(S\) 向车的边满流，并且师傅的修车序列连续（即不会修第 \(1\) 辆车后修第 \(3\) 辆车）因为系数 \(2<3\)，这个由最小费用保证。

代码

#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#define Pair pair <int, int>
using namespace std;

const int N = 66, M = 1e5, lim = 0x3f3f3f3f,maxn=700;
int a[N][N], prev[maxn], pree[maxn], dis[maxn], s, t, n, m, cnt, val[M], flow[M], to[M], head[maxn], nxt[M], h[maxn];

inline int read() {
    int x = 0, f = 1;
    char s = getchar();
    while(! isdigit(s)) {
        if(s == '-')
            f = -1;
        s = getchar();
    }
    while(isdigit(s)) {
        x = (x << 1) + (x << 3) + (s ^ 48);
        s = getchar();
    }
    return x * f;
}

inline void print(int x) {
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}

inline int Min(const int x, const int y) {
	if(x < y)
		return x;
	return y;
}

inline void addEdge(const int u, const int v, const int w) {
	to[++ cnt] = v;
	nxt[cnt] = head[u];
	flow[cnt] = 1;
	val[cnt] = w;
	head[u] = cnt;
	to[++ cnt] = u;
	nxt[cnt] = head[v];
	flow[cnt] = 0;
	val[cnt] = -w;
	head[v] = cnt;
}

int EK() {
	int res = 0, maxflow;
	while(1) {
		priority_queue <Pair, vector <Pair>, greater <Pair> > q;
		memset(dis, 0x3f, sizeof dis);
		dis[s] = 0;
		q.push(Pair(0, s));
		while(! q.empty()) {
			Pair now = q.top();
			q.pop();
			int u = now.second;
			if(dis[u] < now.first)
				continue;
			for(int i = head[u]; ~i; i = nxt[i]) {
				int v = to[i];
				if(flow[i] > 0 && dis[v] > dis[u] + val[i] + h[u] - h[v]) {
					dis[v] = dis[u] + val[i] + h[u] - h[v];
					prev[v] = u;
					pree[v] = i;
					q.push(Pair(dis[v], v));
				}
			}
		}
		if(dis[t] == lim)
			break;
		maxflow = lim;
		for(int i = t; i != s; i = prev[i])
			maxflow = Min(maxflow, flow[pree[i]]);
		res += maxflow * (dis[t] - h[s] + h[t]);
		for(int i = t; i != s; i = prev[i]) {
			flow[pree[i]] -= maxflow;
			flow[pree[i] ^ 1] += maxflow;
		}
		for(int i = 0; i <= m * n; ++ i)
			h[i] += dis[i];
	}
	return res;
}

int pos(const int i, const int j) {
	return (i - 1) * n + j;
}

int main() {
	m = read();
	n = read();
	cnt = 1;
	s = 0;
	t = m*n+n+1;
	memset(head, -1, sizeof head);
	for(int i = 1; i <= n; ++ i)
		for(int j = 1; j <= m; ++ j)
			a[i][j] = read();
	for(int i = 1; i <= m; ++ i)
		for(int j = 1; j <= n; ++ j) {
			for(int k = 1; k <= n; ++ k)
				addEdge(m * n + k, pos(i, j), j * a[k][i]);
			addEdge(pos(i, j), t, 0);
		}
	for(int i = 1; i <= n; ++ i)
		addEdge(s, m * n + i, 0);
	printf("%.2f\n", EK() * 1.0 / (n * 1.0));
	return 0;
}