POJ: The Windy’s

Description

The Windy’s is a world famous toy factory that owns M top-class workshop to make toys. This year the manager receives N orders for toys. The manager knows that every order will take different amount of hours in different workshops. More precisely, the i-th order will take Zij hours if the toys are making in the j-th workshop. Moreover, each order’s work must be wholly completed in the same workshop. And a workshop can not switch to another order until it has finished the previous one. The switch does not cost any time.

The manager wants to minimize the average of the finishing time of the N orders. Can you help him?

Input

The first line of input is the number of test case. The first line of each test case contains two integers, N and M (1 ≤ N,M ≤ 50).
The next N lines each contain M integers, describing the matrix Zij (1 ≤ Zij ≤ 100,000) There is a blank line before each test case.

Output

For each test case output the answer on a single line. The result should be rounded to six decimal places.

Sample Input

3
3 4
100 100 100 1
99 99 99 1
98 98 98 1
3 4
1 100 100 100
99 1 99 99
98 98 1 98
3 4
1 100 100 100
1 99 99 99
98 1 98 98

Sample Output

2.000000
1.000000
1.333333

Problem Analysis:

For minimizing the average of the finishing time of the N orders, we need to get the minimize the total time of the N orders.

If each factory can only make one order, then we can use min cost flow algorithm to solve it.

Suppose there is only one factory, make ith toy need Z_i, then the total time T is T = Z_1 + (Z_1 + Z_2) + … + (Z_1 + Z_2 + … + Z_n)

sequence the items we get

T = N * Z_1 + (N-1) * Z_2 + … + 1 * Z_n

So we can see that we should first make the order of minimize time.

From the above formula, we can regard every item as a factory, but cost 1 to N times of the toy time. So we can use min cost flow algorithm to solve it

#include <cstdio>
#include <vector>
using namespace std;
struct SEdge {
  int to;
  int cap;
  int cost;
  int rev;
  SEdge(int t, int c, int co, int r): to(t), cap(c), cost(co), rev(r) {}
};
#define MAX_N 50
#define MAX_M 50
#define MAX_V ((MAX_N) * (MAX_M) + (MAX_N) + 2)
#define INF 0x3f3f3f3f
int Z[MAX_N][MAX_M];
int n, m;
int V;
vector<SEdge> G[MAX_V];
int dist[MAX_V];
int prevv[MAX_V];
int preve[MAX_V];
void add_edge(int from, int to, int cap, int cost) {
  SEdge fromEdge(to, cap, cost, (int)G[to].size());
  G[from].push_back(fromEdge);
  SEdge toEdge(from, 0, -cost, (int)G[from].size() - 1);
  G[to].push_back(toEdge);
}
int min_cost_flow(int s, int t, int f) {
  int res = 0;
  while (f > 0) {
    fill(dist, dist+V, INF);
    dist[s] = 0;
    bool update = true;
  while (update) {
      update = false;
      for (int v = 0; v < V; ++v) {
        if (dist[v] == INF) continue;
        for (int i = 0; i < G[v].size(); ++i) {
          SEdge& e = G[v][i];
          if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
            dist[e.to] = dist[v] + e.cost;
            prevv[e.to] = v;
            preve[e.to] = i;
            update = true;
          }
        }
      }
    }
    if (dist[t] == INF) return -1;
    int d = f;
    for (int v = t; v != s; v = prevv[v])
      d = min(d, G[prevv[v]][preve[v]].cap);
    f -= d;
    res += d * dist[t];
    for (int v = t; v != s; v = prevv[v]) {
      SEdge& e = G[prevv[v]][preve[v]];
      e.cap -= d;
      G[v][e.rev].cap += d;
    }
  }
  return res;
}
int main(int argc, char *argv[]) {
  int times;
  scanf("%d", &times);
  while (times--) {
    getchar();
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
      getchar();
      for (int j = 0; j < m; ++j) scanf("%d", &Z[i][j]);
    }
    int s = n + n * m;
    int t = s + 1;
    V = t + 1;
      
    for (int i = 0; i < V; ++i) G[i].clear();
    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]);
      }
    }
    printf("%0.6f\n", (double)min_cost_flow(s, t, n) / n);
  }
  return 0;
}

time complexity is O(mn²)

space complexity is O(mn)