题目大意：

传送门

题解：

本题和(POJ3686)[http://poj.org/problem?id=3686]一题一模一样,而且还是数据缩小以后的弱化版QAQ，《挑战程序设计竞赛》一书中有详细解答，我写一下大致的解法。

我们把每个维修员拆成n个点，由每个车子向每个维修员连接n条边，分别代表是该维修员维修的第i个车子。

容易知道，如果车辆i在维修员j处是第k个修的，那么费用就一定会包括k*z[i][j]（车辆i的等待时间也包括在内）。

跑一边费用流就好辣。。

代码

#include <cstdio>

#include <cstring>

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

const int maxn = 65;

const int inf = 0x3f3f3f;

const int maxm = 15;

const int maxv = maxn * maxm * 2;

int z[maxn][maxm];

int n, m, v, s, t;

struct edge {

  int from, to, cap, cost;

};

vector<edge> edges;

vector<int> G[maxn * maxm * 2];

void read() {

  memset(z, 0, sizeof(z));

  scanf("%d %d", &m, &n);

  for (int i = 0; i < n; i++)

    for (int j = 0; j < m; j++)

      scanf("%d", &z[i][j]);

}

int dist[maxv], pre[maxv], a[maxv], inq[maxv];

void add_edge(int s, int t, int cap, int cost) {

  edges.push_back((edge){s, t, cap, cost});

  edges.push_back((edge){t, s, 0, -cost});

  int m = edges.size();

  G[s].push_back(m - 2);

  G[t].push_back(m - 1);

}

bool spfa(int s, int t, int &flow, int &cost) {

  for (int i = 0; i < v; i++)

    dist[i] = inf;

  memset(pre, -1, sizeof(pre));

  memset(inq, 0, sizeof(inq));

  queue<int> q;

  q.push(s);

  dist[s] = 0;

  inq[s] = 1;

  a[s] = inf;

  while (!q.empty()) {

    int v = q.front();

    q.pop();

    inq[v] = 0;

    for (int i = 0; i < G[v].size(); i++) {

      edge &e = edges[G[v][i]];

      if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {

        a[e.to] = min(a[v], e.cap);

        pre[e.to] = G[v][i];

        dist[e.to] = dist[v] + e.cost;

        if (!inq[e.to]) {

          q.push(e.to);

          inq[e.to] = 1;

        }

      }

    }

  }

  if (dist[t] >= inf)

    return false;

  flow += a[t];

  cost += dist[t] * a[t];

  int u = t;

  while (u != s) {

    edges[pre[u]].cap -= a[t];

    edges[pre[u] ^ 1].cap += a[t];

    u = edges[pre[u]].from;

  }

  return true;

}

int mcmf(int s, int t) {

  int flow = 0;

  int cost = 0;

  while (spfa(s, t, flow, cost))

    ;

  return cost;

}

void solve() {

  // 0-n-1 车子

  // n-2n-1 一号工作员

  // 2n-3n-1 二号工作员

  s = n + n * m, t = s + 1, v = t + 1;

  for (int i = 0; i < n; i++)

    add_edge(s, i, 1, 0);

  for (int j = 0; j < m; j++) {

    for (int k = 0; k < n; k++) {

      add_edge(n + j * n + k, t, 1, 0);

      for (int i = 0; i < n; i++) {

        add_edge(i, n + j * n + k, 1, (k + 1) * z[i][j]);

      }

    }

  }

  double ans = (double)mcmf(s, t) / n;

  printf("%.2f\n", ans);

}

int main() {

  read();

  solve();

  return 0;

}