这道题有一个比较神奇的转化。
很显然，我们要求最少总等待时间。
一般而言，我们看见本题，第一反应都是检查选了多少个，来决定第一个的费用。但是，这样存在巨大的后效性，因为我们每多选一个，之后都会被迫都多加上一个，是一个十分的复杂的动态问题。
我们试图将这样一个问题静态化，即我们多选一个只与当前有关，与之前无关。
我们不妨假设当前选的第一个是这个修理员修理的最后一个，那么他产生的贡献就恰好只是他自己的修理时间，当前选的第 (k) 是这个修理员的倒数第 (k) 个，产生的贡献就恰好只是修理时间乘以 (k) 。
至此我们完成来对部分后效性的处理。
现在这个问题被转化成了每个修理员可以选择 (n) 次，第 (k) 次选择中可以选择任何一辆车进行修理也可以不选，代价为修理这辆车的时间乘以 (k) ，同时每辆车最多被选择 (1) 次。
这个问题拥有次数上限必须达到，费用固定的特点，因此这个问题就被转化成为了最小费用最大流的模型，直接建图求解即可。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
template <typename T>
void read(T &x) {
T f=1;x=0;char s=getchar();
while(s<'0'||s>'9') {if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') {x=(x<<3)+(x<<1)+(s^'0');s=getchar();}
x *= f;
}
const int MAXN = 1e6 + 5;
const int MAXM = 1e6 + 5;
const LL inf = 1e15 + 5;
int head[MAXN] , to[MAXM << 1] , nxt[MAXM << 1] , cnt = 1;
LL edge[MAXM << 1] , val[MAXM << 1];
void add(int u , int v , LL c , LL w) {
nxt[++cnt] = head[u];head[u] = cnt;to[cnt] = v;edge[cnt] = c;val[cnt] = w;
nxt[++cnt] = head[v];head[v] = cnt;to[cnt] = u;edge[cnt] = 0;val[cnt] = -w;
}
int s , t , num , cur[MAXN] , vis[MAXN];
LL dis[MAXN];
struct MinCostMaxFlow {
LL MinCost , MaxFlow;
bool bfs() {
for (int i = 1; i <= num; ++i) dis[i] = inf , cur[i] = head[i] , vis[i] = 0;
dis[s] = 0;
queue <int> q;q.push(s);
int flag = 0;
while(!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 0;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if(!edge[i]) continue;
if(dis[v] > dis[x] + val[i]) {
dis[v] = dis[x] + val[i];
if(v == t) {
flag = 1;
continue;
}
if(!vis[v]) vis[v] = 1 , q.push(v);
}
}
}
return flag;
}
LL Dinic(int x , LL flow) {
if(x == t) {
MinCost += dis[x] * flow;
MaxFlow += flow;
return flow;
}
LL rest = flow;
vis[x] = 1;
for (int i = cur[x]; i && rest; i = nxt[i]) {
cur[x] = i;
int v = to[i];
if(!edge[i]) continue;
if(!vis[v] && dis[v] == dis[x] + val[i]) {
LL k = Dinic(v , min(rest , edge[i]));
if(!k) dis[v] = -inf;
edge[i] -= k;
edge[i ^ 1] += k;
rest -= k;
}
}
vis[x] = 0;
return flow - rest;
}
void MVMC() {
MinCost = 0 , MaxFlow = 0;
while(bfs()) Dinic(s , inf);
}
}MIN;
int n , m , T[105][15] , per[15] , car[105];
int main() {
read(m),read(n);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
read(T[i][j]);
}
}
s = 1 , t = 2 , num = 2;
for (int i = 1; i <= m; ++i) add(s , ++num , inf , 0) , per[i] = num;
for (int i = 1; i <= n; ++i) add(++num , t , 1 , 0) , car[i] = num;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
int tmp = ++num;
add(per[i] , tmp , 1 , 0);
for (int k = 1; k <= n; ++k) {
add(tmp , ++num , 1 , T[k][i] * j);
add(num , car[k] , 1 , 0);
}
}
}
MIN.MVMC();
printf("%.2f" , MIN.MinCost * 1.0 / n);
return 0;
}